oj.uz

Submission #552634

# Submission time Handle Problem Language Result Execution time Memory
552634 2022-04-23T13:06:21 Z Awerar A Difficult(y) Choice (BOI21_books) C++17
5 / 100
 1000 ms 473424 KB 
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <limits.h>
#include <math.h>
#include <chrono>
#include <queue>
#include <stack>
#include <algorithm>
#include "books.h"

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define p2 pair<ll, ll>
#define p3 tuple<ll,ll,ll>
#define p4 vi
#define ip3 tuple<int,int,int>
#define ip4 tuple<int,int,int,int>
#define vp2 vector<p2>
#define vp3 vector<p3>
#define inf 2e9
#define linf 1e17

#define read(a) cin >> a
#define write(a) cout << (a) << "\n"
#define dread(type, a) type a; cin >> a
#define dread2(type, a, b) dread(type, a); dread(type, b)
#define dread3(type, a, b, c) dread2(type, a, b); dread(type, c)
#define dread4(type, a, b, c, d) dread3(type, a, b, c); dread(type, d)
#define dread5(type, a, b, c, d, e) dread4(type, a, b, c, d); dread(type, e)
#ifdef _DEBUG
#define deb __debugbreak();
#else
#define deb ;
#endif

#define rep(i, high) for (ll i = 0; i < high; i++)
#define repp(i, low, high) for (ll i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define per(i, high) for (ll i = high; i >= 0; i--)

#define readpush(type,vect) type temp; read(temp); vect.push_back(temp);
#define readvector(type, name, size) vector<type> name(size); rep(i,size) {dread(type,temp); name[i]=temp;}
#define readinsert(type,a) {type temp; read(temp); a.insert(temp);}
#define all(a) begin(a),end(a)
#define setcontains(set, x) (set.find(x) != set.end())
#define stringcontains(str, x) (str.find(x) != string::npos)
#define within(a, b, c, d) (a >= 0 && a < b && c >= 0 && c < d)

#define ceildiv(x,y) ((x + y - 1) / y)
#define fract(a) (a-floor(a))
#define sign(a) ((a>0) ? 1 : -1)

//auto Start = chrono::high_resolution_clock::now();

inline void fast()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

long long books[110000];
unordered_set<long long> visited;

vector<int> dp(int i, long long sum, vector<int>* choice, long long k, long long A, long long N) {
    if(choice->size() == k) {
        if(sum >= A && sum <= 2 * A) return vector<int>(choice->begin(), choice->end());
        else return {};
    }

    if(i < 0 || sum > 2 * A) return {};

    long long id = sum * N * k + i * k + choice->size();
    if (setcontains(visited, id)) return {};

    vector<int> result;

    choice->push_back(i + 1);
    result = dp(i - 1, sum + books[i], choice, k, A, N);
    choice->pop_back();

    if(result.size() > 0) return result;

    result = dp(i - 1, sum, choice, k, A, N);
    
    visited.insert(id);
    return result;
}

void solve(int N, int K, long long A, int S) {
    for(int i = 0; i < N; i++) {
        books[i] = skim(i+1);
    }

    auto res = dp(N - 1, 0, new vector<int>(), K, A, N);
    if(res.size() == 0) impossible();
    else answer(res);
}

Compilation message

books.cpp:19: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   19 | #pragma GCC optimization ("O3")
      | 
books.cpp:20: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   20 | #pragma GCC optimization ("unroll-loops")
      | 
books.cpp: In function 'std::vector<int> dp(int, long long int, std::vector<int>*, long long int, long long int, long long int)':
books.cpp:77:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   77 |     if(choice->size() == k) {
      |        ~~~~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 10 ms 592 KB Output is correct
3 Correct 9 ms 316 KB Output is correct
4 Correct 8 ms 300 KB Output is correct
5 Correct 10 ms 432 KB Output is correct
6 Correct 8 ms 440 KB Output is correct
7 Correct 9 ms 464 KB Output is correct
8 Correct 164 ms 52956 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 4 ms 576 KB Output is correct
3 Correct 8 ms 308 KB Output is correct
4 Correct 9 ms 208 KB Output is correct
5 Correct 9 ms 464 KB Output is correct
6 Correct 8 ms 312 KB Output is correct
7 Correct 6 ms 440 KB Output is correct
8 Correct 187 ms 53000 KB Output is correct
9 Correct 365 ms 59704 KB Output is correct
10 Correct 185 ms 6684 KB Output is correct
11 Correct 125 ms 4196 KB Output is correct
12 Correct 168 ms 476 KB Output is correct
13 Correct 163 ms 8692 KB Output is correct
14 Correct 205 ms 612 KB Output is correct
15 Execution timed out 3036 ms 473424 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -