Submission #998128
Source Code Expand
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }
template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
int c=0;
while ( *s!=',' || c!=0 ) {
if ( *s=='(' || *s=='[' || *s=='{' ) c++;
if ( *s==')' || *s==']' || *s=='}' ) c--;
cerr<<*s++;
}
cerr<<"="<<head<<", ";
_dump(s+1,tail...);
}
#define dump(...) do { \
fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
_dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)
template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
s<<"[";
for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
s<<"]";
return s;
}
template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif
template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }
void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
_R(head);
R(tail...);
}
template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
if ( i!=x.cbegin() ) putchar(' ');
_W(*i);
}
}
void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
_W(head);
putchar(sizeof...(tail)?' ':'\n');
W(tail...);
}
#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
freopen(name ".in","r",stdin); \
freopen(name ".out","w",stdout); \
} while (0)
#endif
// }}}
const int N=1e5+10;
const LL INF=9e18;
int n,m,t;
LL a[N],dp[N],ndp[N];
int main() {
R(n,m,t);
REP1(i,1,n) R(a[i]);
// REP1(i,1,n) dp[i]=-INF;
REP1(i,1,t) {
REP1(j,0,n) if ( dp[j]<0 ) dp[j]=-INF;
deque<pair<LL,int>> q;
q.push_back({dp[0],0});
REP1(j,1,n) {
while ( !q.empty() && q.front().second<j-m ) q.pop_front();
// LL mx=*max_element(dp+max(0,j-m),dp+j);
LL mx=q.front().first;
ndp[j]=mx+i*a[j];
while ( !q.empty() && q.back().first<=dp[j] ) q.pop_back();
q.push_back({dp[j],j});
}
ndp[0]=-INF;
memcpy(dp,ndp,sizeof(dp));
}
dump(vector<LL>(dp,dp+n));
LL ans=*max_element(dp+1,dp+n+1);
assert(ans>0);
W(ans);
return 0;
}
Submission Info
Submission Time
2016-11-27 11:17:24+0900
Task
A - Struck Out
User
shik
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
3666 Byte
Status
AC
Exec Time
472 ms
Memory
2560 KB
Compile Error
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
void _R( long long &x ) { scanf("%" PRId64,&x); }
^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:61:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void _R( int &x ) { scanf("%d",&x); }
^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void _R( long long &x ) { scanf("%" PRId64,&x); }
^
./Main.cpp: In function ‘void _R(double&)’:
./Main.cpp:63:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-resu...
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
4 ms
1024 KB
sample_2.txt
AC
4 ms
1024 KB
sample_3.txt
AC
4 ms
1024 KB
subtask_1_1.txt
AC
5 ms
1024 KB
subtask_1_2.txt
AC
51 ms
1152 KB
subtask_1_3.txt
AC
400 ms
2560 KB
subtask_1_4.txt
AC
7 ms
1152 KB
subtask_1_5.txt
AC
23 ms
2560 KB
subtask_1_6.txt
AC
12 ms
1024 KB
subtask_1_7.txt
AC
144 ms
2560 KB
subtask_1_8.txt
AC
400 ms
2560 KB
subtask_1_9.txt
AC
17 ms
1024 KB
subtask_2_1.txt
AC
5 ms
1024 KB
subtask_2_2.txt
AC
4 ms
1024 KB
subtask_2_3.txt
AC
4 ms
1024 KB
subtask_2_4.txt
AC
5 ms
1024 KB
subtask_2_5.txt
AC
5 ms
1024 KB
subtask_2_6.txt
AC
5 ms
1024 KB
subtask_2_7.txt
AC
5 ms
1024 KB
subtask_2_8.txt
AC
5 ms
1024 KB
subtask_2_9.txt
AC
5 ms
1024 KB
subtask_3_1.txt
AC
55 ms
2560 KB
subtask_3_2.txt
AC
56 ms
2560 KB
subtask_3_3.txt
AC
54 ms
2560 KB
subtask_3_4.txt
AC
46 ms
2304 KB
subtask_3_5.txt
AC
7 ms
1152 KB
subtask_3_6.txt
AC
39 ms
2560 KB
subtask_3_7.txt
AC
55 ms
2560 KB
subtask_3_8.txt
AC
10 ms
1152 KB
subtask_3_9.txt
AC
61 ms
2560 KB
subtask_4_1.txt
AC
400 ms
2560 KB
subtask_4_10.txt
AC
400 ms
2560 KB
subtask_4_11.txt
AC
472 ms
2560 KB
subtask_4_12.txt
AC
470 ms
2560 KB
subtask_4_13.txt
AC
464 ms
2560 KB
subtask_4_2.txt
AC
458 ms
2560 KB
subtask_4_3.txt
AC
399 ms
2560 KB
subtask_4_4.txt
AC
400 ms
2560 KB
subtask_4_5.txt
AC
345 ms
2560 KB
subtask_4_6.txt
AC
46 ms
2560 KB
subtask_4_7.txt
AC
247 ms
2560 KB
subtask_4_8.txt
AC
398 ms
2560 KB
subtask_4_9.txt
AC
205 ms
2560 KB