oj.uz

Submission #523334

# Submission time Handle Problem Language Result Execution time Memory
523334 2022-02-07T13:19:43 Z ac2hu Modsum (NOI12_modsum) C++14
25 / 25
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
signed main() {
	#define ll long long 
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int n;cin >> n;
	vector<pair<int,int>> inp(n);
	for(auto &e : inp)
		cin >> e.first >> e.second;
	// We can solve this problem by finding the number of sums with k mod 5
	vector<array<int,5>> dp(n);
	vector<array<int,5>> count(n,{0,0,0,0,0});
	for(int i =0 ;i<n;i++){
		for(int j = inp[i].first;j<=inp[i].second;j++){
			count[i][(j%5)]++;
		}
	}
	// Calculating dp[0];
	for(int a1 = 0;a1<5;a1++)
		dp[0][a1] = count[0][a1];
	for(int i = 1;i<n;i++){
		dp[i] = {0,0,0,0,0};
		for(int al = 0;al<5;al++){
			for(int bl = 0;bl<5;bl++){
				dp[i][(al + bl)%5] += dp[i - 1][al]*count[i][bl];
			}
		}	
	}
	ll ans = 0;
	for(int al = 0;al<5;al++){
		if(al == 0)
			ans += dp[n - 1][al];
		else if(al == 1 || al == 4)
			ans += 4*dp[n - 1][al];
		else
			ans += 5*dp[n - 1][al];
	}
	cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 312 KB Output is correct