oj.uz

Submission #648626

# Submission time Handle Problem Language Result Execution time Memory
648626 2022-10-07T08:15:11 Z penguin133 Modsum (NOI12_modsum) C++14
25 / 25
 49 ms 1108 KB 
#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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 3 ms 980 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1076 KB Output is correct
2 Correct 8 ms 1076 KB Output is correct
3 Correct 10 ms 980 KB Output is correct
4 Correct 8 ms 1080 KB Output is correct
5 Correct 9 ms 980 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1040 KB Output is correct
2 Correct 15 ms 1036 KB Output is correct
3 Correct 15 ms 980 KB Output is correct
4 Correct 15 ms 1040 KB Output is correct
5 Correct 18 ms 1036 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 712 KB Output is correct
2 Correct 42 ms 724 KB Output is correct
3 Correct 43 ms 728 KB Output is correct
4 Correct 39 ms 724 KB Output is correct
5 Correct 42 ms 724 KB Output is correct