제출 #1124720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124720		Matjaz	나머지들의 합 (NOI12_modsum)	C++20	25 / 25	1 ms	328 KiB

modsum

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5