oj.uz

Submission #278017

# Submission time Handle Problem Language Result Execution time Memory
278017 2020-08-21T08:50:51 Z 반딧불(#5119) Shopping Plans (CCO20_day2problem3) C++17
0 / 25
 4000 ms 251236 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

struct dat{
    ll a, b, c, d;
    dat(ll a, ll b, ll c, ll d): a(a), b(b), c(c), d(d){}
    bool operator<(const dat &r)const{
        return a>r.a;
    }
};

int n, m, k;
vector<ll> arr[4002];
priority_queue<dat> pq;
ll ans[4002];
ll weight[4002];
vector<int> ansVec[4002];
set<ll> st;
ll sum = 0;

ll hsh(vector<int>& v){
    ll ret = 0;
    for(auto &x: v) ret *= 26137, ret += x, ret %= 1000000007;
    return ret;
}

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1; i<=n; i++){
        int x; ll y;
        scanf("%d %lld", &x, &y);
        arr[x].push_back(y);
    }
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
    }

    for(int i=1; i<=m; i++) sort(arr[i].begin(), arr[i].end());
    for(int i=1; i<=m; i++){
        if(arr[i].empty()){
            while(k--) printf("-1\n");
            return 0;
        }
        sum += arr[i][0];
    }

    for(int i=0; i<m; i++){
        weight[i] = rand();
    }

    vector<int> zeroVec (m, 0);
    st.insert(0);
    pq.push(dat(sum, 0, 0, 0));

    for(int d=1; d<=k; d++){
        if(pq.empty()) break;
        auto tmp = pq.top(); pq.pop();

        vector<int> tv;
        if(!tmp.b) tv = zeroVec;
        else{
            tv = ansVec[tmp.b];
            tv[tmp.c]++;
        }
        ansVec[d] = tv;

        ans[d] = tmp.a;
        for(int i=0; i<m; i++){
            if(tv[i] == (int)arr[i+1].size()-1) continue;
            tv[i]++;
            ll tsh = tmp.d + weight[i] * (arr[i+1][tv[i]] - arr[i+1][tv[i]-1]);
            if(st.find(tsh) == st.end())
                st.insert(tsh), pq.push(dat(tmp.a + arr[i+1][tv[i]] - arr[i+1][tv[i]-1], d, i, tsh));
            tv[i]--;
        }
    }

    for(int d=1; d<=k; d++){
        printf("%lld\n", ans[d] ? ans[d] : -1);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |         scanf("%d %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4073 ms 251236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4078 ms 250340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4073 ms 251236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4073 ms 251236 KB Time limit exceeded
2 Halted 0 ms 0 KB -