Submission #905394
Source Code Expand
#define NDEBUG #undef __STRICT_ANSI__ #include <cstdlib> #include <cstdio> #include <tuple> #include <vector> #include <algorithm> #include <functional> #include <cstring> #include <cmath> #include <cfloat> #include <cassert> using namespace std; #undef assert #define assert(e) #include <cstdarg> typedef long long int64; #include <sys/time.h> class XsRandom { unsigned long long a; unsigned long long b; public: inline XsRandom() : a(0x8a5cd789635d2dffULL), b(0x121fd2155c472f96ULL) { } inline XsRandom(const XsRandom & o) : a(o.a), b(o.b) { } inline unsigned long long next64() { unsigned long long c = a ^ (a<<23); a = b; b = c ^ a ^ (c>>18) ^ (a>>5); return b + a; } inline XsRandom(unsigned int seed) : a(0x8a5cd789635d2dffULL), b(0x121fd2155c472f96ULL) { seed = seed * 1234567891 + 521288629; unsigned long long a2 = a; unsigned long long b2 = b; while(seed) { next64(); if(seed & 1) { a2 ^= a; b2 ^= b; } seed >>= 1; } a = a2; b = b2; } inline unsigned int next() { return (unsigned int)next64(); } inline int nextInt(int r) { assert(1<=r); return ((unsigned long long)next() * r)>>32; } }; typedef XsRandom MyRandom; MyRandom g_myRand; double g_startTime; double g_suspendTime = 0; const double g_timeupSecBase = 9.8; double g_timeupSec = g_timeupSecBase; #include <numeric> const char * nextCLineOrWord(int mode) { static char buf[565536]; static int bufLen = sizeof(buf); static int bufPos = sizeof(buf); static bool canReadFlag = true; static bool crFlag = false; static bool enterFlag = false; if(canReadFlag && (enterFlag ? bufLen<=bufPos : (int)sizeof(buf)<=bufPos+bufPos)) { if(0<bufLen-bufPos) { memmove(buf, buf+bufPos, bufLen-bufPos); bufLen -= bufPos; } else { bufLen = 0; } char * result = fgets(buf+bufLen, sizeof(buf)-bufLen, stdin); canReadFlag = (result!=NULL); if(result!=NULL) { int n = strlen(result); enterFlag = (n!=(int)sizeof(buf)-1-bufLen || (1<=bufLen+n && buf[bufLen+n-1]=='\n')); bufLen += n; } bufPos = 0; } if(mode==0) { int pos = bufPos; while(true) { char c = buf[pos]; if(c==32) { buf[pos++] = '\0'; break; } else if(c==10) { if(crFlag) { crFlag = false; if(bufPos==pos) { pos = ++bufPos; continue; } } buf[pos++] = '\0'; break; } else if(c==13) { crFlag = true; buf[pos++] = '\0'; break; } else if(c==0) { break; } ++pos; } const char * ret = buf + bufPos; bufPos = pos; while(true) { char c = buf[bufPos]; if(c==32 || c==10 || c==13) { ++bufPos; } else { break; } } return ret; } else if(mode==1) { int pos = bufPos; while(true) { char c = buf[pos]; if(c==10) { if(crFlag) { crFlag = false; if(bufPos==pos) { pos = ++bufPos; continue; } } buf[pos++] = '\0'; break; } else if(c==13) { crFlag = true; buf[pos++] = '\0'; break; } else if(c==0) { break; } ++pos; } const char * ret = buf + bufPos; bufPos = pos; if(crFlag) { while(true) { char c = buf[bufPos]; if(c==13) { ++bufPos; crFlag = false; break; } else { break; } } } return ret; } else if(mode==2) { return bufLen<=bufPos ? NULL : buf+bufPos; } assert(false); return NULL; } const char * nextCWord() { return nextCLineOrWord(0); } int nextInt() { return atoi(nextCWord()); } vector<int> nextIntVec(int n) { vector<int> ret; for(int i=0; i<n; ++i) { ret.push_back(nextInt()); } return ret; } void echoln() { fputc('\n', stdout); } void echoln(const char * fmt, ...) { va_list arg; va_start(arg, fmt); vprintf(fmt, arg); va_end(arg); fputc('\n', stdout); } int main() { vector<int> a = nextIntVec(nextInt()); vector<int> b(a.size()); int64 sum = 0; for(int l=0; l<(int)a.size(); ++l) { int m = a[l]; int ll = l; for(int r=l; r<(int)a.size(); ++r) { if(a[r]<m) { m = a[r]; b[ll] = r; ll = r; if(r<b[r]) { sum += (int64)m * (b[r]-r+1); continue; } } sum += m; } } echoln("%lld", sum); return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | colun |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 4416 Byte |
Status | WA |
Exec Time | 2102 ms |
Memory | 2420 KB |
Judge Result
Set Name | Sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2 |
All | corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
corner0 | TLE | 2102 ms | 2420 KB |
corner1 | TLE | 2102 ms | 2420 KB |
corner2 | AC | 2 ms | 256 KB |
corner3 | TLE | 2102 ms | 2420 KB |
example0 | AC | 2 ms | 256 KB |
example1 | AC | 2 ms | 256 KB |
example2 | AC | 2 ms | 256 KB |
maxrand0 | TLE | 2102 ms | 2420 KB |
maxrand1 | TLE | 2102 ms | 2420 KB |
maxrand2 | TLE | 2102 ms | 2420 KB |
rand0 | WA | 2 ms | 256 KB |
rand1 | WA | 2 ms | 256 KB |
rand2 | WA | 2 ms | 256 KB |