Submission #998021
Source Code Expand
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<map> #include<set> #include<utility> #include<cmath> #include<cstring> #include<queue> #include<stack> #include<cstdio> #include<sstream> #include<iomanip> #define loop(i,a,b) for(int i=a;i<b;i++) #define rep(i,a) loop(i,0,a) #define pb push_back #define mp make_pair #define all(in) in.begin(),in.end() #define shosu(x) fixed<<setprecision(x) using namespace std; //kaewasuretyuui typedef long long ll; typedef pair<int,int> pii; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<pii> vp; typedef vector<vp> vvp; typedef vector<string> vs; typedef vector<double> vd; typedef pair<int,pii> pip; typedef vector<pip>vip; const double PI=acos(-1); const double EPS=1e-8; const ll inf=1e15; typedef ll SegT; const int defvalue=0; class SegTree{ private: vector<SegT>val; ll n; SegT combine(SegT a,SegT b){return max(a,b);} public: SegTree(ll size){ n=1; while(n<size)n<<=1; val=vector<SegT>(2*n,defvalue); } SegTree(const vector<SegT> &in){ n=1; while(n<in.size())n<<=1; val=vector<SegT>(2*n,defvalue); for(int i=n-1+in.size()-1;i>=0;i--){ if(n-1<=i)val[i]=in[i-(n-1)]; else val[i]=combine(val[i*2+1],val[i*2+2]); } } void update(int i,SegT a){ i+=n-1; val[i]=a; while(i>0){ i=(i-1)/2; val[i]=combine(val[i*2+1],val[i*2+2]); } } SegT query(int a,int b,int k=0,int l=0,int r=-1){//[a,b) if(r==-1)r=n; if(r<=a||b<=l)return defvalue; if(a<=l&&r<=b)return val[k]; else return combine(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r)); } void tmp(){ rep(i,val.size())cout<<" "<<val[i];cout<<endl; } }; int main(){ int n,m,q; cin>>n>>m>>q; vi in(n); rep(i,n)cin>>in[i]; SegTree st(in); rep(i,q-1){ for(int j=n-1;j>=0;j--){ st.update(j,(i+2)*in[j]+st.query(j-m,j)); } } cout<<st.query(0,n); }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | ixmel_rd |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1995 Byte |
Status | WA |
Exec Time | 2102 ms |
Memory | 3200 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 | 2 ms | 256 KB |
sample_2.txt | AC | 2 ms | 256 KB |
sample_3.txt | AC | 2 ms | 256 KB |
subtask_1_1.txt | AC | 3 ms | 256 KB |
subtask_1_2.txt | AC | 436 ms | 640 KB |
subtask_1_3.txt | TLE | 2102 ms | 3072 KB |
subtask_1_4.txt | AC | 26 ms | 384 KB |
subtask_1_5.txt | AC | 111 ms | 3072 KB |
subtask_1_6.txt | WA | 5 ms | 256 KB |
subtask_1_7.txt | AC | 1677 ms | 3072 KB |
subtask_1_8.txt | TLE | 2102 ms | 3072 KB |
subtask_1_9.txt | WA | 15 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 | WA | 2 ms | 256 KB |
subtask_2_6.txt | WA | 2 ms | 256 KB |
subtask_2_7.txt | AC | 3 ms | 256 KB |
subtask_2_8.txt | AC | 4 ms | 256 KB |
subtask_2_9.txt | AC | 3 ms | 256 KB |
subtask_3_1.txt | AC | 657 ms | 3072 KB |
subtask_3_2.txt | AC | 781 ms | 3072 KB |
subtask_3_3.txt | AC | 764 ms | 3072 KB |
subtask_3_4.txt | AC | 621 ms | 2944 KB |
subtask_3_5.txt | AC | 24 ms | 384 KB |
subtask_3_6.txt | AC | 359 ms | 3072 KB |
subtask_3_7.txt | AC | 559 ms | 3072 KB |
subtask_3_8.txt | AC | 73 ms | 512 KB |
subtask_3_9.txt | AC | 693 ms | 3072 KB |
subtask_4_1.txt | TLE | 2102 ms | 3072 KB |
subtask_4_10.txt | TLE | 2102 ms | 3072 KB |
subtask_4_11.txt | TLE | 2102 ms | 3072 KB |
subtask_4_12.txt | TLE | 2102 ms | 3072 KB |
subtask_4_13.txt | TLE | 2102 ms | 3200 KB |
subtask_4_2.txt | TLE | 2102 ms | 3072 KB |
subtask_4_3.txt | TLE | 2102 ms | 3072 KB |
subtask_4_4.txt | TLE | 2102 ms | 3072 KB |
subtask_4_5.txt | TLE | 2102 ms | 3072 KB |
subtask_4_6.txt | AC | 407 ms | 3072 KB |
subtask_4_7.txt | TLE | 2102 ms | 3072 KB |
subtask_4_8.txt | TLE | 2102 ms | 3072 KB |
subtask_4_9.txt | TLE | 2102 ms | 3072 KB |