Submission #1555623
Source Code Expand
#pragma region include #include <iostream> #include <iomanip> #include <stdio.h> #include <sstream> #include <algorithm> #include <iterator> #include <cmath> #include <complex> #include <string> #include <cstring> #include <vector> #include <tuple> #include <bitset> #include <queue> #include <complex> #include <set> #include <map> #include <stack> #include <list> #include <fstream> #include <random> //#include <time.h> #include <ctime> #pragma endregion //#include ///////// #define REP(i, x, n) for(int i = x; i < n; ++i) #define rep(i,n) REP(i,0,n) #define ALL(X) X.begin(), X.end() ///////// #pragma region typedef typedef long long LL; typedef long double LD; typedef unsigned long long ULL; typedef std::pair<LL,LL> PLL;// typedef std::pair<int,int> PII;// #pragma endregion //typedef ////定数 const int INF = (int)1e9; const LL MOD = (LL)1e9+7; const LL LINF = (LL)1e18+20; const LD PI = acos(-1.0); const double EPS = 1e-9; ///////// using namespace::std; template <typename T> class segment_base{ int N;//要素数 vector< T > dat1; T VAL_E;//初期値 public: segment_base(){}; segment_base(int n,T val_E ):N(n),VAL_E(val_E){ dat1.resize(2*n); dat1.assign(2*n,val_E);//初期化 } void init(int n,T val_E){ N = n; VAL_E = val_E; dat1.resize(2*n); dat1.assign(2*n,val_E); } T SELECT(T L,T R){//扱う演算子 T ans; ans = max(L,R);// return ans; } //index番目の値をvalに変更,indexは"0-index" void update(int index,T val){ for(dat1[index+=N] = val;index>1;index>>=1){ dat1[index>>1] = SELECT(dat1[index],dat1[index^1]);//index+0,+1 } } //区間[L,R)のSELECT T query(int L,int R){ T ans = VAL_E;// for(L+=N,R+=N; L<R;L>>=1,R>>=1){ if(L&1) ans = SELECT(ans,dat1[L++]); if(R&1) ans = SELECT(ans,dat1[--R]); } return ans; } }; void solve(){ int N,M,K; cin >> N >> M >> K; vector<LL> A(N); for(int i=0;i<N;++i){ cin >> A[i]; } segment_base< LL > seg(N+1,-1); seg.update(0,0); for(LL k=1;k<=K;++k){ for(int i=N;i>=1;--i){ //k-1回目からiにこれる点の最大値 LL res = seg.query( max(0,i-M), i );//右半開 if( res < 0 ) continue; res += k * A[i-1];//k回目の得点 seg.update(i,res); } } LL ans = seg.query(K,N+1); cout << ans << endl; } #pragma region main signed main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;//小数を10進数表示 cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別 solve(); } #pragma endregion //main()
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | akarin55 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2654 Byte |
Status | WA |
Exec Time | 2103 ms |
Memory | 2560 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, 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 | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 1 ms | 256 KB |
subtask_1_2.txt | AC | 225 ms | 512 KB |
subtask_1_3.txt | TLE | 2103 ms | 2560 KB |
subtask_1_4.txt | AC | 12 ms | 384 KB |
subtask_1_5.txt | AC | 52 ms | 2560 KB |
subtask_1_6.txt | WA | 2 ms | 256 KB |
subtask_1_7.txt | AC | 820 ms | 2560 KB |
subtask_1_8.txt | TLE | 2103 ms | 2560 KB |
subtask_1_9.txt | WA | 7 ms | 256 KB |
subtask_2_1.txt | AC | 2 ms | 256 KB |
subtask_2_2.txt | WA | 1 ms | 256 KB |
subtask_2_3.txt | AC | 1 ms | 256 KB |
subtask_2_4.txt | AC | 1 ms | 256 KB |
subtask_2_5.txt | WA | 1 ms | 256 KB |
subtask_2_6.txt | WA | 1 ms | 256 KB |
subtask_2_7.txt | AC | 1 ms | 256 KB |
subtask_2_8.txt | AC | 2 ms | 256 KB |
subtask_2_9.txt | AC | 1 ms | 256 KB |
subtask_3_1.txt | AC | 264 ms | 2560 KB |
subtask_3_2.txt | AC | 203 ms | 2560 KB |
subtask_3_3.txt | AC | 226 ms | 2560 KB |
subtask_3_4.txt | WA | 168 ms | 2176 KB |
subtask_3_5.txt | AC | 11 ms | 384 KB |
subtask_3_6.txt | WA | 32 ms | 2560 KB |
subtask_3_7.txt | AC | 256 ms | 2560 KB |
subtask_3_8.txt | AC | 24 ms | 512 KB |
subtask_3_9.txt | WA | 52 ms | 2560 KB |
subtask_4_1.txt | TLE | 2103 ms | 2560 KB |
subtask_4_10.txt | WA | 101 ms | 2560 KB |
subtask_4_11.txt | WA | 231 ms | 2560 KB |
subtask_4_12.txt | WA | 290 ms | 2560 KB |
subtask_4_13.txt | WA | 377 ms | 2560 KB |
subtask_4_2.txt | WA | 735 ms | 2560 KB |
subtask_4_3.txt | TLE | 2103 ms | 2560 KB |
subtask_4_4.txt | TLE | 2103 ms | 2560 KB |
subtask_4_5.txt | AC | 1940 ms | 2560 KB |
subtask_4_6.txt | AC | 198 ms | 2560 KB |
subtask_4_7.txt | WA | 465 ms | 2560 KB |
subtask_4_8.txt | TLE | 2103 ms | 2560 KB |
subtask_4_9.txt | AC | 860 ms | 2560 KB |