Submission #833877

#	Time	Username	Problem	Language	Result	Execution time	Memory
833877		Liudas	Arcade (NOI20_arcade)	C++17	30 / 100	1064 ms	324160 KiB

Arcade

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
struct button{
    int A, T;
    bool operator<(const button &x)const{
        return T < x.T;
    }
};
int best = 300;
set<vector<button>> seen;
void BFS(int B, vector<button> &arr, vector<button> used){
    if(B == arr.size()){
        best = used.size();
        return;
    }
    if(used.size() >= best){
        return;
    }
    for(button &i : used){
        if(abs(arr[B].A-i.A) <= arr[B].T-i.T){
            button t = i;
            i = arr[B];
            if(seen.find(used)!=seen.end()){i=t; continue;}
            seen.insert(used);
            BFS(B+1, arr, used);
            i = t;
        }
        if(used.size() >= best)return;
    }
    used.push_back(arr[B]);
    if(seen.find(used)!=seen.end())return;
    seen.insert(used);
    BFS(B+1, arr, used);
}
int main(){
    int N, M;
    cin >> N >> M;
    vector<button> arr(M);
    for(int i = 0; i < M; i ++){
        cin >> arr[i].T;
    }
    for(int j = 0; j < M; j ++){
        cin >> arr[j].A;
    }
    sort(arr.begin(), arr.end());
    vector<button> used;
    used.push_back(arr[0]);
    BFS(0, arr, used);
    cout << best << endl;
    return 0;
}

Compilation message (stderr)

Arcade.cpp: In function 'void BFS(int, std::vector<button>&, std::vector<button>)':
Arcade.cpp:15:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<button>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if(B == arr.size()){
      |        ~~^~~~~~~~~~~~~
Arcade.cpp:19:20: warning: comparison of integer expressions of different signedness: 'std::vector<button>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |     if(used.size() >= best){
      |        ~~~~~~~~~~~~^~~~~~~
Arcade.cpp:31:24: warning: comparison of integer expressions of different signedness: 'std::vector<button>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |         if(used.size() >= best)return;
      |            ~~~~~~~~~~~~^~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 14
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15