Submission #648626

#	Time	Username	Problem	Language	Result	Execution time	Memory
648626		penguin133	Modsum (NOI12_modsum)	C++14	25 / 25	49 ms	1108 KiB

modsum

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
#define getchar_unlocked _getchar_nolock
int n,m;
pi A[1005];
int dp[100005];
void solve(){
	cin >> n;
	int cnt = 0;
	for(int i=1;i<=n;i++)cin >> A[i].fi >> A[i].se, cnt += A[i].fi;
	dp[cnt] = 1;
	for(int i=1;i<=n;i++){
		int sum = 0;
		int x = A[i].se - A[i].fi;
		for(int j=100000;j>=100000-x;j--)sum += dp[j];
		for(int j=100000;j>=cnt;j--){
			int tmp = sum;
			sum += dp[j-x-1];
			sum -= dp[j-1];
			dp[j] += tmp;
		}
	}
	int ans = 0;
	for(int i=1;i<=100000;i++){
		int x = i * i;
		int y = (x + 1 ) * (x + 1);
		y %= 5;
		if(!y)y = 5;
		ans += y * dp[i];
	}
	cout << ans;
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

modsum.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~

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