oj.uz

답안 #661084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
661084 2022-11-24T09:02:17 Z mychecksedad 메기 농장 (IOI22_fish) C++17
12 / 100
 466 ms 123612 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 1e5 + 100;


vector<ll> dp[N][2], pref[N][3], dp_pref[N], dp_suf[N], dp_pref_max[N]; //pref:  0 : itself, 1 : left one, 2 : right one
vector<int> v[N], p[N];

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y, std::vector<int> w){  

    for(int i = 0; i < m; ++i){
        v[x[i]].pb(i);
        if(x[i] > 0) v[x[i] - 1].pb(i);
        if(x[i] < n - 1) v[x[i] + 1].pb(i);
    }

    for(int i = 0; i <= n; ++i){
        int s = v[i].size() + 1;
        for(int a: v[i]) p[i].pb(y[a] + 1);
        p[i].pb(0);
        sort(p[i].begin(), p[i].end());
        for(int k = 0; k < 3; ++k){
            pref[i][k].resize(s);
        }
        dp[i][0].resize(s);
        dp[i][1].resize(s);
        dp_pref[i].resize(s);
        dp_suf[i].resize(s);
        dp_pref_max[i].resize(s);

        vector<pair<int, int>> all;
        for(int a: v[i]) all.pb({y[a] + 1, a});
        sort(all.begin(), all.end());
        for(pair<int, int> &a: all){
            a.first = lower_bound(all.begin(), all.end(), make_pair(a.first, -1)) - all.begin() + 1;
            if(x[a.second] == i) pref[i][0][a.first] += w[a.second];
            else if(x[a.second] == i - 1) pref[i][1][a.first] += w[a.second];
            else pref[i][2][a.first] += w[a.second];
        }   
        for(int k = 0; k < 3; ++k)
            for(int j = 1; j < pref[i][k].size(); ++j) pref[i][k][j] += pref[i][k][j - 1];
    }

    for(int i = 0; i <= n; ++i){
        int s = pref[i][0].size();
        for(int j = 0; j < s; ++j){    
            if(i == 0){
                dp[i][0][j] = dp[i][1][j] = pref[i][2][j];
                continue;
            }

            dp[i][0][j] = pref[i][2][j];

            int pos = upper_bound(p[i - 1].begin(), p[i - 1].end(), p[i][j]) - p[i - 1].begin() - 1;


            if(i == 1){
                dp[i][0][j] += dp_pref[i - 1][pos] + pref[i][1][j];
            }else{  
                int pos2 = upper_bound(p[i - 2].begin(), p[i - 2].end(), p[i][j]) - p[i - 2].begin() - 1;
                dp[i][0][j] += max({dp_pref[i - 1][pos] + pref[i - 1][0][pos],
                    dp_suf[i - 2][0],
                    dp_pref_max[i - 2][pos2] + pref[i - 1][0][pos] 
                });
            }
            int pos3 = lower_bound(p[i - 1].begin(), p[i - 1].end(), p[i][j]) - p[i - 1].begin();
            dp[i][1][j] = pref[i][2][j] - pref[i][0][j] + (pos3 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos3]);
        }

        for(int j = 0; j < s; ++j){
            if(j == 0){
                dp_pref[i][j] = dp[i][0][j] - pref[i][2][j] - pref[i][0][j];
                dp_pref_max[i][j] = max(dp[i][0][j], dp[i][1][j]) - pref[i][2][j];
            }
            else{
                dp_pref[i][j] = max(dp_pref[i][j - 1], dp[i][0][j] - pref[i][2][j] - pref[i][0][j]);
                dp_pref_max[i][j] = max(dp_pref_max[i][j - 1], max(dp[i][0][j], dp[i][1][j]) - pref[i][2][j]);
            }
        }

        for(int j = s - 1; j >= 0; --j){
            if(j == s - 1){
                dp_suf[i][j] = max(dp[i][0][j], dp[i][1][j]);
            }
            else{
                dp_suf[i][j] = max({dp_suf[i][j + 1], dp[i][0][j], dp[i][1][j]});
            }
        }
    }
    return dp_suf[n][0];
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:43:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int j = 1; j < pref[i][k].size(); ++j) pref[i][k][j] += pref[i][k][j - 1];
      |                            ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:69:65: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             dp[i][1][j] = pref[i][2][j] - pref[i][0][j] + (pos3 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos3]);
      |                                                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 62400 KB Output is correct
2 Correct 174 ms 68332 KB Output is correct
3 Correct 74 ms 51860 KB Output is correct
4 Correct 80 ms 51940 KB Output is correct
5 Correct 466 ms 123612 KB Output is correct
6 Correct 443 ms 116312 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 250 ms 81644 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40577210384051'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 51888 KB Output is correct
2 Correct 88 ms 51968 KB Output is correct
3 Correct 121 ms 57768 KB Output is correct
4 Correct 107 ms 57912 KB Output is correct
5 Correct 170 ms 69904 KB Output is correct
6 Correct 177 ms 69864 KB Output is correct
7 Correct 175 ms 69996 KB Output is correct
8 Correct 174 ms 69868 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 15 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23744 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23848 KB Output is correct
10 Incorrect 16 ms 24424 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '799486576522'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 15 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23744 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23848 KB Output is correct
10 Incorrect 16 ms 24424 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '799486576522'
11 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 15 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23744 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23848 KB Output is correct
10 Incorrect 16 ms 24424 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '799486576522'
11 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 51888 KB Output is correct
2 Correct 88 ms 51968 KB Output is correct
3 Correct 121 ms 57768 KB Output is correct
4 Correct 107 ms 57912 KB Output is correct
5 Correct 170 ms 69904 KB Output is correct
6 Correct 177 ms 69864 KB Output is correct
7 Correct 175 ms 69996 KB Output is correct
8 Correct 174 ms 69868 KB Output is correct
9 Correct 172 ms 69856 KB Output is correct
10 Correct 123 ms 56256 KB Output is correct
11 Correct 294 ms 88760 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 12 ms 23708 KB Output is correct
14 Correct 12 ms 23776 KB Output is correct
15 Correct 14 ms 23808 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 14 ms 23764 KB Output is correct
18 Correct 73 ms 51856 KB Output is correct
19 Correct 84 ms 52088 KB Output is correct
20 Correct 93 ms 51916 KB Output is correct
21 Correct 75 ms 51968 KB Output is correct
22 Correct 202 ms 67792 KB Output is correct
23 Incorrect 265 ms 88696 KB 1st lines differ - on the 1st token, expected: '77772396150817', found: '82247868011018'
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 62400 KB Output is correct
2 Correct 174 ms 68332 KB Output is correct
3 Correct 74 ms 51860 KB Output is correct
4 Correct 80 ms 51940 KB Output is correct
5 Correct 466 ms 123612 KB Output is correct
6 Correct 443 ms 116312 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 250 ms 81644 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40577210384051'
9 Halted 0 ms 0 KB -