Submission #1079307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079307		_rain_	Coin Collecting (JOI19_ho_t4)	C++14	8 / 100	229 ms	181192 KiB

joi2019_ho_t4

#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] = min(dp[t][mask] , dp[t - 1][mask^MASK(i)] + 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 (stderr)

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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63