# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
527684 | 2022-02-18T02:32:22 Z | jamielim | Calvinball championship (CEOI15_teams) | C++14 | 83 ms | 628 KB |
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb emplace_back #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() typedef long long ll; typedef pair<int,int> ii; typedef pair<ii,ii> i4; const int MOD=1000000007; const int INF=1012345678; const ll LLINF=1012345678012345678LL; const double PI=3.1415926536; const double EPS=1e-14; const int mod=1000007; int n; ll arr[10005]; ll premax[10005]; ll dp[2][10005]; int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lld",&arr[i]); if(i==0)premax[i]=arr[i]; else premax[i]=max(premax[i-1],arr[i]); } ll ans=1; // all equal (final day) for(int i=1;i<=n-1;i++){ dp[(n-1)&1][i]=1; } ans+=(arr[n-1]-1)*dp[(n-1)&1][premax[n-2]]; ans%=mod; //printf("%lld\n",ans); for(int i=n-2;i>=1;i--){ for(int j=1;j<=i;j++){ dp[i&1][j]=dp[(i+1)&1][j]+dp[(i+1)&1][j+1]; dp[i&1][j]%=mod; } ans+=(arr[i]-1)*dp[i&1][premax[i-1]]; ans%=mod; //printf("%lld\n",ans); } printf("%lld",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 284 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Incorrect | 1 ms | 296 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 312 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 300 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 83 ms | 628 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 460 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 83 ms | 612 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |