제출 #1068696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068696		hasan2006	Catfish Farm (IOI22_fish)	C++17	9 / 100	1066 ms	592208 KiB

fish

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 4e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , c[N];
deque<pair<int,int>>v[N];
vector<ll>dp[N] , d[N];

ll max_weights(int n, int m , vector<int>a , vector<int>b , vector<int>c){
    ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;

    for(i = 0; i < m; i++)
        v[a[i]].pb({b[i], c[i]});
    for(i = 0; i < n; i++){
        sort(all(v[i]));
        if(v[i].size() == 0 || v[i].front().fi != 0)
            v[i].push_front({0 , 0});
        v[i].pb({n , 0});
        d[i].resize(v[i].size() , 0);
        dp[i].resize(v[i].size() , 0);
        if(i == 0)
        continue;
        l = 0 , s= 0;
        for(j = 0; j < v[i].size(); j++){
            while(l < v[i - 1].size() && v[i - 1][l].fi < v[i][j].fi)
                s += v[i - 1][l].se , l++;
            f = 0;
            for(x = 0; x < l; x++)
                dp[i][j] = max(dp[i][j] , dp[i - 1][x] + s - f) , f += v[i - 1][x].se;
            if(v[i][l].fi == v[i][j].fi)
                dp[i][j] = max(dp[i][j] , max(dp[i - 1][l] , d[i - 1][l]));
            r = l;
            f = 0;
            if(i > 1)
                for(x = 0; x < v[i - 2].size(); x++){
                    while(r < v[i - 1].size() && v[i - 1][r].fi < v[i - 2][x].fi)
                        f += v[i - 1][r].se , r++;
                    dp[i][j] = max(dp[i][j] , s + f + max(dp[i - 2][x] , d[i - 2][x]));
                }
            f = 0 , r = j;
            for(x = 0; x < v[i - 1].size(); x++){
                while(r < v[i].size() && v[i][r].fi < v[i - 1][x].fi)
                    f += v[i][r].se , r++,
                d[i][j] = max(d[i][j] , max(dp[i - 1][x] , d[i - 1][x]) + f);
                dp[i][j] = max(dp[i][j] , max(dp[i - 1][x] , d[i - 1][x]));
            }
            d[i][j] = max(d[i][j] , dp[i][j]);
            ans = max({ans , dp[i][j] , d[i][j]});
        }
    }
    return ans;
}
/*
int main(){
    TL;

    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    cout<<max_weights(6, 5, {5, 4, 0 , 2 , 1}, {0, 0, 0 , 0 , 0}, {979169285 ,288589606,  56346688 , 568303254 , 617066964});
}*/
// Author : حسن

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:41:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
fish.cpp:42:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while(l < v[i - 1].size() && v[i - 1][l].fi < v[i][j].fi)
      |                   ~~^~~~~~~~~~~~~~~~~
fish.cpp:52:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                 for(x = 0; x < v[i - 2].size(); x++){
      |                            ~~^~~~~~~~~~~~~~~~~
fish.cpp:53:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                     while(r < v[i - 1].size() && v[i - 1][r].fi < v[i - 2][x].fi)
      |                           ~~^~~~~~~~~~~~~~~~~
fish.cpp:58:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(x = 0; x < v[i - 1].size(); x++){
      |                        ~~^~~~~~~~~~~~~~~~~
fish.cpp:59:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 while(r < v[i].size() && v[i][r].fi < v[i - 1][x].fi)
      |                       ~~^~~~~~~~~~~~~
fish.cpp:27:40: warning: unused variable 'y' [-Wunused-variable]
   27 |     ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
      |                                        ^
fish.cpp:27:44: warning: unused variable 'k' [-Wunused-variable]
   27 |     ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
      |                                            ^

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16