Submission #1097021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097021		hgmhc	만두 (JOI14_ho_t2)	C++17	100 / 100	17 ms	860 KiB

2014_ho_t2

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
using namespace std;
using ll = long long;

const int M = 10003, N = 503;
int m, n;
int p[M];
int c[N], e[N];
ll dp[M+M], sfx[M+M];

int main() {
    scanf("%d%d", &m, &n);
    rep(i,1,m) scanf("%d", &p[i]);
    sort(p+1,p+m+1,greater<>());
    rep(i,1,n) scanf("%d%d", &c[i], &e[i]);
    fill(dp,dp+M+M,1e18);
    fill(sfx,sfx+M+M,1e18);
    dp[0] = 0;
    int mx = *max_element(p+1,p+m+1);
    rep(j,1,n) per(i,0,m+M) {
        if (i >= c[j])
            mup(dp[i],dp[i-c[j]]+e[j]);
    }
    ll ans = 0, pfx = 0;
    per(i,0,m+M) sfx[i] = min(sfx[i-1],dp[i]);
    rep(i,0,m+M) {
        if (i <= m) pfx += p[i];
        Mup(ans, pfx - sfx[i]);
    }
    printf("%lld", ans);
}

Compilation message (stderr)

2014_ho_t2.cpp: In function 'int main()':
2014_ho_t2.cpp:23:9: warning: unused variable 'mx' [-Wunused-variable]
   23 |     int mx = *max_element(p+1,p+m+1);
      |         ^~
2014_ho_t2.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d", &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~
2014_ho_t2.cpp:17:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     rep(i,1,m) scanf("%d", &p[i]);
      |                ~~~~~^~~~~~~~~~~~~
2014_ho_t2.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     rep(i,1,n) scanf("%d%d", &c[i], &e[i]);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40