oj.uz

답안 #411170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411170 2021-05-24T13:12:16 Z 반딧불(#7588) 여별 열쇠 (JOI15_keys) C++14
100 / 100
 2 ms 1484 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int x, t, m; /// m=0: start, m=1: end
    dat(){}
    dat(int x, int t, int m): x(x), t(t), m(m){}
    bool operator<(const dat &r)const{
        return t<r.t;
    }
};
vector<dat> vec;

int n, m, k;
int s[2002], e[2002];
int ans;

int weight[2002];
vector<pair<int, int> > link[2002];

int renum[2002], loc[2002], locCnt;
int w[2002], bet[2002];

int DP[2002][2002][2];
int basic;

void dfsRenum(int x){
    int tmp = ++locCnt;
    renum[tmp] = x;
    loc[x] = tmp;
    w[tmp] = weight[x];

    for(auto y: link[x]){
        if(loc[y.first]) continue;
        bet[tmp] = y.second;
        dfsRenum(y.first);
    }
}

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &s[i], &e[i]);
        vec.push_back(dat(i, s[i], 0));
        vec.push_back(dat(i, e[i], 1));
    }
    sort(vec.begin(), vec.end());

    basic = vec[0].t;
    for(int i=0; i<2*n-1; i++){
        dat p = vec[i], q = vec[i+1];
        if(!p.m && !q.m) weight[p.x] += q.t - p.t;
        else if(p.m && q.m) weight[q.x] += q.t - p.t;
        else if(!p.m && q.m){
            if(p.x == q.x) weight[p.x] += q.t - p.t;
            else{
                link[p.x].push_back(make_pair(q.x, q.t - p.t));
                link[q.x].push_back(make_pair(p.x, q.t - p.t));
            }
        }
        else basic += q.t - p.t;
    }
    basic += m - vec.back().t;

    for(int i=1; i<=n; i++){
        if((int)link[i].size() >= 2 || loc[i]) continue;
        dfsRenum(i);
    }
    assert(locCnt == n);

    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) DP[i][j][0] = DP[i][j][1] = -1e9;
    for(int i=0; i<=n; i++) DP[i][0][0] = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            DP[i][j][0] = max(DP[i-1][j][0], DP[i-1][j][1]);
            DP[i][j][1] = max(DP[i-1][j-1][0] + w[i], DP[i-1][j-1][1] + w[i] + bet[i-1]);
        }
    }
    printf("%d", max(DP[n][k][0], DP[n][k][1]) + basic);
}

Compilation message

keys.cpp: In function 'int main()':
keys.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
keys.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d %d", &s[i], &e[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 1100 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct
15 Correct 2 ms 1484 KB Output is correct
16 Correct 2 ms 1484 KB Output is correct
17 Correct 1 ms 1484 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 1 ms 1356 KB Output is correct
20 Correct 1 ms 1484 KB Output is correct
21 Correct 1 ms 1484 KB Output is correct
22 Correct 1 ms 1356 KB Output is correct
23 Correct 2 ms 1484 KB Output is correct
24 Correct 1 ms 1484 KB Output is correct