Submission #12987

#	Time	Username	Problem	Language	Result	Execution time	Memory
12987		gs14004	코알라 (JOI13_koala)	C++98	20 / 100	2000 ms	2648 KiB

koala

#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 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50