QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#640133 | #2929. Concert Rehearsal | enze114514 | TL | 509ms | 3868kb | C++20 | 1.5kb | 2024-10-14 06:53:31 | 2024-10-14 06:53:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
const ld pi = 3.14159265358979323846;
const int mod = 998244353;
const ll INF = 1e18;
template<typename T>
T chmax(T a, T b) {
return a > b ? a : b;
}
template<typename T>
T chmin(T a, T b) {
return a > b ? b : a;
}
const int N = (int)1e5 + 1, M = N * 2;
void solve() {
int n;
ll p, k;
cin >> n >> p >> k;
vector<int> d(n);
for (int i = 0; i < n; ++i) {
cin >> d[i];
}
int idx = 0;
ll day = 0, ps = 0, t = p;
typedef pair<int, ll> st;
map<st, pair<ll, ll>> mp;
st s = {idx, t};
mp[s] = {day, ps};
while(day < k){
while(t >= d[idx]){
t -= d[idx];
idx++;
if (idx == n) {
idx = 0;
ps++;
}
}
day++;
t = p;
s = {idx, t};
if(mp.count(s)){
ll pday = mp[s].first, prev = mp[s].second;
ll clen = day - pday, cp = ps - prev;
ll rem = k - day;
ll cyc = rem / clen;
ps += cyc * cp;
day += cyc * clen;
}
else{
mp[s] = {day, ps};
}
}
cout << ps << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
input:
3 20 10 6 9 5
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
5 11 2 5 5 5 5 5
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
7 11 3 1 2 3 4 5 6 7
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
4 8 9 2 7 2 3
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1 3 7 2
output:
7
result:
ok single line: '7'
Test #6:
score: 0
Accepted
time: 462ms
memory: 3492kb
input:
1 1000000000 1000000000 1
output:
1000000000000000000
result:
ok single line: '1000000000000000000'
Test #7:
score: 0
Accepted
time: 509ms
memory: 3604kb
input:
5 999999999 999999999 2 1 4 7 3
output:
58823528941176471
result:
ok single line: '58823528941176471'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
5 5 1000 2 2 2 2 2
output:
400
result:
ok single line: '400'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
980 991 978 2 1 2 1 2 3 1 1 1 3 3 3 2 2 2 2 3 3 1 3 1 2 2 3 1 2 3 3 2 3 1 2 2 3 1 3 1 3 2 2 2 1 1 2 3 3 1 2 1 1 1 2 2 2 3 3 2 1 3 3 1 3 3 1 1 2 1 1 1 1 2 1 2 3 2 1 1 3 3 2 2 1 3 3 3 2 2 3 1 2 3 3 2 2 3 2 3 2 2 2 1 3 3 1 1 3 1 2 2 2 2 1 2 2 1 1 3 2 1 1 3 1 2 3 3 3 3 3 2 2 2 3 3 1 1 2 1 3 3 3 2 2 2 3 ...
output:
492
result:
ok single line: '492'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
980 967 994 6 1 4 6 10 10 8 5 5 9 2 8 10 1 8 7 10 1 7 3 7 1 4 10 2 5 7 5 2 5 4 9 4 9 8 1 9 8 9 8 4 1 3 2 4 9 4 2 8 7 5 7 9 9 1 4 10 10 3 7 5 4 1 1 6 7 8 6 6 9 9 9 10 10 9 10 9 10 7 9 4 3 9 8 3 5 2 1 3 5 9 3 6 4 10 8 2 2 8 4 2 4 8 1 2 9 1 2 6 10 3 4 9 9 9 10 10 10 2 6 2 5 5 7 10 9 9 3 10 8 4 9 6 3 10...
output:
179
result:
ok single line: '179'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
995 997 962 48 41 40 40 41 50 45 43 42 49 40 49 43 50 50 47 47 48 41 43 40 43 41 43 41 49 43 46 41 48 45 42 44 47 44 46 44 46 40 42 43 45 43 45 40 41 49 41 45 40 48 43 50 48 45 43 50 46 44 48 50 48 44 44 42 41 48 50 49 41 48 48 48 46 45 43 47 48 49 48 41 40 46 44 43 40 42 44 43 46 43 43 47 42 43 40 ...
output:
21
result:
ok single line: '21'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
962 981 996 85 234 239 585 600 759 968 366 415 610 749 684 701 524 796 720 733 404 182 216 856 378 210 643 306 203 831 212 413 171 568 562 406 793 475 937 64 958 209 81 563 566 810 531 903 600 820 914 395 502 216 673 573 882 604 161 720 461 43 105 822 406 476 446 60 285 268 795 637 561 129 962 619 3...
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
992 965 983 567 702 416 603 427 787 855 407 646 406 964 869 518 484 721 455 539 433 440 695 376 932 704 794 928 946 642 607 897 592 336 904 852 458 377 618 645 800 512 924 840 745 819 791 539 520 750 896 452 441 573 678 377 927 789 425 458 318 628 564 738 580 347 861 913 407 833 721 421 849 941 415 ...
output:
1
result:
ok single line: '1'
Test #14:
score: -100
Time Limit Exceeded
input:
191517 972629409 971799494 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...