oj.uz

Submission #1079305

# Submission time Handle Problem Language Result Execution time Memory
1079305 2024-08-28T12:52:26 Z _rain_ Coin Collecting (JOI19_ho_t4) C++14
0 / 100
 90 ms 180916 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fixbug false

void SETIO(string name = ""){
    if (name=="") return;
    freopen((name+".inp").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
    return;
}
#define fi first
#define se second

#define MASK(x) ((ll)(1)<<(x))
#define BIT(mask,x) (((mask)>>(x))&(1))
const int maxn = 20;
ll dp[maxn+2][MASK(maxn)];
int n , x[maxn+2] , y[maxn+2];
vector<pair<int,int>> p;

int cost(int x1 , int y1 , int x2 , int y2){
    return abs(x1 - x2) + abs(y1 - y2);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    SETIO("");

    cin >> n;
    for (int i = 1; i <= 2*n; ++i) cin >> x[i] >> y[i];
    memset(dp,0x3f,sizeof dp);
    for (int i = 1; i <= n; ++i) for (int j = 1 ; j <= 2; ++j) p.push_back({i,j});
    dp[0][0] = 0;
    for (int t = 1; t <= 2*n; ++t) {
        for (int mask = 0; mask < MASK(2*n); ++mask){
            if (__builtin_popcount(mask)!=t) continue;
            for (int i = 0; i < 2 * n; ++i) if (!BIT(mask,i)){
                dp[t][mask|MASK(i)] = min(dp[t][mask|MASK(i)] , dp[t - 1][mask] + cost(p[i].fi , p[i].se , x[t] , y[t]));
            }
        }
    }
    if (fixbug){
        cout << "(DEBUG)\n";
        for (int layer = 1; layer <= 2 * n; ++layer){
            for (int mask = 0; mask < MASK(2*n); ++mask){
                cout << dp[layer][mask] << ' ';
            }
            cout << '\n';
        }
    }
    cout << dp[2 * n][MASK(2 * n) - 1];
}

Compilation message

joi2019_ho_t4.cpp: In function 'void SETIO(std::string)':
joi2019_ho_t4.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen((name+".inp").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 63.0

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