oj.uz

Submission #12987

# Submission time Handle Problem Language Result Execution time Memory
12987 2015-01-23T03:58:27 Z gs14004 코알라 (JOI13_koala) C++
20 / 100
 2000 ms 2648 KB 
#include <cstdio>
#include <algorithm>
using namespace std;

int d,c,n;
int a[100005], b[100005];
long long dp[100005];

int main(){
    int s,e;
    scanf("%d %d %d %d %d",&s,&e,&d,&c,&n);
    for (int i=1; i<=n; i++) {
        scanf("%d %d",&a[i],&b[i]);
        a[i] -= s;
    }
    a[n+1] = e-s;
    for (int i=n; i>=0; i--) {
        dp[i] = -1e18;
        for (int j=i+1; j<=n+1; j++) {
            dp[i] = max(dp[i],dp[j] - 1ll * (a[j] - a[i] + d - 1) / d * c);
        }
        dp[i] += b[i];
    }
    printf("%lld",dp[0]);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2648 KB Output is correct
2 Correct 8 ms 2648 KB Output is correct
3 Correct 4 ms 2648 KB Output is correct
4 Correct 0 ms 2648 KB Output is correct
5 Correct 8 ms 2648 KB Output is correct
6 Correct 8 ms 2648 KB Output is correct
7 Correct 0 ms 2648 KB Output is correct
8 Correct 4 ms 2648 KB Output is correct
9 Correct 8 ms 2648 KB Output is correct
10 Correct 8 ms 2648 KB Output is correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 2644 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 2644 KB Program timed out
2 Halted 0 ms 0 KB -