Submission #998599
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef int _loop_int; #define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i) #define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i) #define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i) #define DEBUG(x) cout<<#x<<": "<<x<<endl #define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl #define ALL(a) (a).begin(),(a).end() #define CHMIN(a,b) a=min((a),(b)) #define CHMAX(a,b) a=max((a),(b)) // mod const ll MOD = 1000000007ll; #define FIX(a) ((a)%MOD+MOD)%MOD // floating typedef double Real; const Real EPS = 1e-11; #define EQ0(x) (abs(x)<EPS) #define EQ(a,b) (abs(a-b)<EPS) typedef complex<Real> P; int n,m,k; int a[125252]; ll dp[2][125252]; int main(){ scanf("%d%d%d",&n,&m,&k); REP(i,n)scanf("%d",a+i); int cur = 0; cur ^= 1; REP(j,k){ // slide max int r=0; deque<int> Q; REP(i,n){ while(r<=n && r<=i+m){ while(!Q.empty() && dp[cur^1][Q.back()] <= dp[cur^1][r]) Q.pop_back(); Q.push_back(r++); } while(Q.front() <= i)Q.pop_front(); dp[cur][i] = (ll)(k-j)*a[i] + (Q.empty()? 0 : dp[cur^1][Q.front()]); } cur ^= 1; } ll ans = 0; REP(i,n)CHMAX(ans,dp[cur^1][i]); cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | rickytheta |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1475 Byte |
Status | AC |
Exec Time | 466 ms |
Memory | 2304 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:39:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&n,&m,&k); ^ ./Main.cpp:40:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] REP(i,n)scanf("%d",a+i); ^
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 200 / 200 | 300 / 300 | 100 / 100 | ||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 | sample_2.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
subtask3 | sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt, subtask_4_1.txt, subtask_4_10.txt, subtask_4_11.txt, subtask_4_12.txt, subtask_4_13.txt, subtask_4_2.txt, subtask_4_3.txt, subtask_4_4.txt, subtask_4_5.txt, subtask_4_6.txt, subtask_4_7.txt, subtask_4_8.txt, subtask_4_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | AC | 3 ms | 256 KB |
sample_2.txt | AC | 3 ms | 256 KB |
sample_3.txt | AC | 3 ms | 256 KB |
subtask_1_1.txt | AC | 3 ms | 256 KB |
subtask_1_2.txt | AC | 45 ms | 512 KB |
subtask_1_3.txt | AC | 428 ms | 2304 KB |
subtask_1_4.txt | AC | 5 ms | 384 KB |
subtask_1_5.txt | AC | 23 ms | 2304 KB |
subtask_1_6.txt | AC | 3 ms | 256 KB |
subtask_1_7.txt | AC | 151 ms | 2176 KB |
subtask_1_8.txt | AC | 429 ms | 2304 KB |
subtask_1_9.txt | AC | 4 ms | 256 KB |
subtask_2_1.txt | AC | 3 ms | 256 KB |
subtask_2_2.txt | AC | 3 ms | 256 KB |
subtask_2_3.txt | AC | 3 ms | 256 KB |
subtask_2_4.txt | AC | 3 ms | 256 KB |
subtask_2_5.txt | AC | 3 ms | 256 KB |
subtask_2_6.txt | AC | 3 ms | 256 KB |
subtask_2_7.txt | AC | 3 ms | 256 KB |
subtask_2_8.txt | AC | 3 ms | 256 KB |
subtask_2_9.txt | AC | 3 ms | 256 KB |
subtask_3_1.txt | AC | 57 ms | 2176 KB |
subtask_3_2.txt | AC | 58 ms | 2176 KB |
subtask_3_3.txt | AC | 56 ms | 2176 KB |
subtask_3_4.txt | AC | 47 ms | 1792 KB |
subtask_3_5.txt | AC | 5 ms | 384 KB |
subtask_3_6.txt | AC | 38 ms | 2176 KB |
subtask_3_7.txt | AC | 56 ms | 2176 KB |
subtask_3_8.txt | AC | 8 ms | 512 KB |
subtask_3_9.txt | AC | 59 ms | 2176 KB |
subtask_4_1.txt | AC | 443 ms | 2304 KB |
subtask_4_10.txt | AC | 366 ms | 2176 KB |
subtask_4_11.txt | AC | 466 ms | 2176 KB |
subtask_4_12.txt | AC | 461 ms | 2176 KB |
subtask_4_13.txt | AC | 457 ms | 2176 KB |
subtask_4_2.txt | AC | 453 ms | 2176 KB |
subtask_4_3.txt | AC | 431 ms | 2304 KB |
subtask_4_4.txt | AC | 445 ms | 2304 KB |
subtask_4_5.txt | AC | 380 ms | 2176 KB |
subtask_4_6.txt | AC | 47 ms | 2176 KB |
subtask_4_7.txt | AC | 246 ms | 2176 KB |
subtask_4_8.txt | AC | 437 ms | 2176 KB |
subtask_4_9.txt | AC | 204 ms | 2176 KB |