Submission #997900
Source Code Expand
#include <string> #include <vector> #include<iostream> #include<cstdio> #include<cstdlib> #include<stack> #include<queue> #include<cmath> #include<algorithm> #include<functional> #include<list> #include<deque> #include<bitset> #include<set> #include<map> #include<unordered_map> #include<unordered_set> #include<cstring> #include<sstream> #include<complex> #include<iomanip> #include<numeric> #include<cassert> #define X first #define Y second #define pb push_back #define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X)) #define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X)) #define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X)) #define repe(X,Y) for ((X) = 0;(X) < (Y);++(X)) #define peat(X,Y) for (;(X) < (Y);++(X)) #define all(X) (X).begin(),(X).end() #define rall(X) (X).rbegin(),(X).rend() #define eb emplace_back #define UNIQUE(X) (X).erase(unique(all(X)),(X).end()) using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<class T> using vv=vector<vector<T>>; template<class T> ostream& operator<<(ostream &os, const vector<T> &t) { os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;} template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";} template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;} template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;} const ll MOD=1e9+7; ll dp[333][112345]; int main(){ ios_base::sync_with_stdio(false); cout<<fixed<<setprecision(0); int n,m,t; cin>>n>>m>>t; vector<ll> a(n); rep(i,n) cin>>a[i]; deque<pll> que[333]; rep(i,n)rep(j,t){ while(que[j].size() && que[j].back().X<=dp[j][i]) que[j].pop_back(); que[j].eb(dp[j][i],i); while(i-que[j].front().Y>=t) que[j].pop_front(); dp[j+1][i+1]=que[j].front().X+(j+1)*a[i]; } //rep(i,t+1){rep(j,n+1)cout<<dp[i][j]<<",";cout<<endl;} cout<<*max_element(dp[t],dp[t]+n+1)<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | nuip |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2045 Byte |
Status | WA |
Exec Time | 869 ms |
Memory | 236928 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 0 / 200 | 0 / 300 | 0 / 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 | 512 KB |
sample_2.txt | AC | 3 ms | 512 KB |
sample_3.txt | AC | 3 ms | 512 KB |
subtask_1_1.txt | AC | 3 ms | 640 KB |
subtask_1_2.txt | AC | 85 ms | 25216 KB |
subtask_1_3.txt | WA | 865 ms | 236928 KB |
subtask_1_4.txt | WA | 6 ms | 1920 KB |
subtask_1_5.txt | WA | 24 ms | 5248 KB |
subtask_1_6.txt | WA | 5 ms | 1536 KB |
subtask_1_7.txt | WA | 235 ms | 79872 KB |
subtask_1_8.txt | WA | 864 ms | 236928 KB |
subtask_1_9.txt | WA | 9 ms | 2816 KB |
subtask_2_1.txt | WA | 3 ms | 640 KB |
subtask_2_2.txt | AC | 3 ms | 512 KB |
subtask_2_3.txt | WA | 3 ms | 640 KB |
subtask_2_4.txt | AC | 3 ms | 640 KB |
subtask_2_5.txt | WA | 3 ms | 640 KB |
subtask_2_6.txt | WA | 3 ms | 640 KB |
subtask_2_7.txt | WA | 3 ms | 640 KB |
subtask_2_8.txt | WA | 3 ms | 640 KB |
subtask_2_9.txt | WA | 3 ms | 640 KB |
subtask_3_1.txt | WA | 69 ms | 24832 KB |
subtask_3_2.txt | WA | 69 ms | 24832 KB |
subtask_3_3.txt | WA | 67 ms | 24064 KB |
subtask_3_4.txt | WA | 56 ms | 19968 KB |
subtask_3_5.txt | WA | 6 ms | 1792 KB |
subtask_3_6.txt | WA | 42 ms | 13056 KB |
subtask_3_7.txt | WA | 69 ms | 24832 KB |
subtask_3_8.txt | WA | 10 ms | 3072 KB |
subtask_3_9.txt | WA | 69 ms | 24832 KB |
subtask_4_1.txt | WA | 858 ms | 236928 KB |
subtask_4_10.txt | WA | 869 ms | 236928 KB |
subtask_4_11.txt | WA | 865 ms | 236928 KB |
subtask_4_12.txt | WA | 858 ms | 236928 KB |
subtask_4_13.txt | WA | 858 ms | 236928 KB |
subtask_4_2.txt | WA | 853 ms | 236928 KB |
subtask_4_3.txt | WA | 857 ms | 236928 KB |
subtask_4_4.txt | WA | 860 ms | 236928 KB |
subtask_4_5.txt | WA | 696 ms | 200832 KB |
subtask_4_6.txt | WA | 57 ms | 19328 KB |
subtask_4_7.txt | WA | 379 ms | 125440 KB |
subtask_4_8.txt | WA | 834 ms | 233984 KB |
subtask_4_9.txt | WA | 319 ms | 104960 KB |