500C - New Year Book Reading - CodeForces Solution


constructive algorithms greedy implementation math *1600

Please click on ads to support us..

Python Code:

n, m = map(int,input().split())
w = list(map(int, input().split())) + [0]
b = [(int(x)-1) for x in input().split()]
ans = 0
for i in range(m):
    for j in range(i-1,-1,-1):
        if b[j] == b[i]:
            b[j] = n
            break
        ans += w[b[j]]
print(ans)

C++ Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

 
const int maxn = 1e6 + 10;
const int MOD = 1e9+7;


int a[maxn], last[maxn], mark[maxn];

void solve(){

	int n, m;
	cin>> n>> m;
	

	for(int i = 0; i < n; i++){
		cin>> a[i + 1];
	}
	int x;
	cin>> x;
	
	vector<int>vec;
	vec.pb(x);
	
	for(int i = 1; i < m; i++){
		cin>> x;
		if(x != vec.back())	vec.pb(x);
	}
	
	int ans = 0;
	int sum = 0;
	int cnt = 1;
	for(int u: vec){
//if(last[u]) cout<<"||||||||||"<< u<< endl;
		int sum1 = 0;
		fill(mark, mark + n + 1, 0);
		for(int i = last[u]; i < cnt - 1; i++){
			if(!mark[vec[i]]){
				//if(!last[u]) cout<<a[vec[i]] <<" ";
				sum1+= a[vec[i]];
				mark[vec[i]] = 1;
			}
	
		}
		//cout<< endl;
		last[u] = cnt;
		ans += sum1;
		//cout<< sum1 << endl;
		cnt++;
	}
	cout<< ans ;
	
}
int main(){
	
	solve();
	return 0;	
}


Comments

Submit
0 Comments
More Questions

1654A - Maximum Cake Tastiness
1649A - Game
139A - Petr and Book
1612A - Distance
520A - Pangram
124A - The number of positions
1041A - Heist
901A - Hashing Trees
1283A - Minutes Before the New Year
1654D - Potion Brewing Class
1107B - Digital root
25A - IQ test
785A - Anton and Polyhedrons
1542B - Plus and Multiply
306A - Candies
1651C - Fault-tolerant Network
870A - Search for Pretty Integers
1174A - Ehab Fails to Be Thanos
1169A - Circle Metro
780C - Andryusha and Colored Balloons
1153A - Serval and Bus
1487C - Minimum Ties
1136A - Nastya Is Reading a Book
1353B - Two Arrays And Swaps
1490E - Accidental Victory
1335A - Candies and Two Sisters
96B - Lucky Numbers (easy)
1151B - Dima and a Bad XOR
1435B - A New Technique
1633A - Div 7