Submission #1124720

#TimeUsernameProblemLanguageResultExecution timeMemory
1124720MatjazModsum (NOI12_modsum)C++20
25 / 25
1 ms328 KiB
#include <iostream>
#include <vector>
using namespace std;

int main(){

	int N;
	cin >> N;
	vector<int> v(N), w(N);
	for (int i=0;i<N;i++){
		cin >> v[i] >> w[i];
	}

	vector<int> values(5);
	for (int i=0;i<5;i++) values[i] = (i * i * i * i + 2 * i * i) % 5 + 1;

	//for (int i=0;i<5;i++) cout << values[i] << endl;

	vector<vector<long long> > count_ways(N, vector<long long> (5));
	vector<vector<long long> > count_choices(N, vector<long long> (5));

	for (int i=0;i<N;i++){
		for (int j=v[i];j<=w[i];j++){
			count_choices[i][j % 5]++;
		}
	}

	for (int i=0;i<5;i++) count_ways[N-1][i] = count_choices[N-1][i];

	for (int i=N-2;i>=0;i--){
		for (int j=0;j<5;j++){
			for (int k=0;k<5;k++){
				count_ways[i][j] += count_ways[i+1][(5 + j - k) % 5] * count_choices[i][k];
			}
		}
	}


	long long result = 0;
	for (int i=0;i<5;i++) result += values[i] * count_ways[0][i];

	//for (int i=0;i<5;i++) cout << count_ways[0][i] << endl;

	cout << result << endl;

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...