JOI予選のこり

結果も発表されたことだし実装しますた

問５

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, k;
int d[50][6];
int cnt[105][105][105];
vector<int> xx, yy, dd;
map<int, int> idx, idy, idd, dix, diy, did;
int main() {
    scanf("%d%d",&n,&k);
    for (int i=0; i<n; i++) {
        scanf("%d%d%d%d%d%d",
                &d[i][0],&d[i][1],&d[i][2],&d[i][3],&d[i][4],&d[i][5]);
        xx.push_back(d[i][0]); xx.push_back(d[i][3]);
        yy.push_back(d[i][1]); yy.push_back(d[i][4]);
        dd.push_back(d[i][2]); dd.push_back(d[i][5]);
    }
    sort(xx.begin(), xx.end());
    sort(yy.begin(), yy.end());
    sort(dd.begin(), dd.end());
    int idn=0, idm=0, ido=0;
    dix[0]=xx[0]; diy[0]=yy[0]; did[0]=dd[0];
    for (int i=1; i<xx.size(); i++) {
        if (dix[idn]!=xx[i]) idn++;
        idx[xx[i]] = idn;
        dix[idn]=xx[i];
    }
    for (int i=1; i<yy.size(); i++) {
        if (diy[idm]!=yy[i]) idm++;
        idy[yy[i]] = idm;
        diy[idm]=yy[i];
    }
    for (int i=1; i<dd.size(); i++) {
        if (did[ido]!=dd[i]) ido++;
        idd[dd[i]] = ido;
        did[ido]=dd[i];
    }
    for (int i=0; i<n; i++) {
        for (int j=idx[d[i][0]]; j<idx[d[i][3]]; j++) {
            for (int l=idy[d[i][1]]; l<idy[d[i][4]]; l++) {
                for (int m=idd[d[i][2]]; m<idd[d[i][5]]; m++) cnt[j][l][m]++;
            }
        }
    }
    ll res=0;
    for (int i=0; i<idn; i++) {
        for (int j=0; j<idm; j++) {
            for (int l=0; l<ido; l++) {
                if (cnt[i][j][l]>=k) res+=((ll)(dix[i+1]-dix[i])*(ll)(diy[j+1]-diy[j])*(ll)(did[l+1]-did[l]));
            }
        }
    }
    printf("%lld\n",res);
}

1801
347149566041429203
124015464949851877
991380998439054609
65264947770876113

問６

実装なぜだか苦戦したｗ
…ではなくバグ死なう。kagamizさんとsnukeさんのコード参考にしてほぼ違いないコードなのになぜかサンプルさえ通らない

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MA (1<<12)-1
int h, w, k;
string mp[50];
int dp[1<<12][5][55][55];
// 0(00) up 1(01) left 2(10) down 3(11) right
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

int dfs(int move, int waste, int x, int y) {
    if (dp[move][waste][x][y]!=-1) return dp[move][waste][x][y];
    int nmv = (move<<2)&MA;

    int valt=-999999;

    for (int i=0; i<4; i++) {
        if (waste>=k&&i<2) continue;
        int nx=x+dx[i], ny=y+dy[i];
        if (0>nx||h<=nx||0>ny||w<=ny||mp[nx][ny]=='#') continue;
        valt=max(valt, dfs(nmv|i, waste+(i<2), nx, ny));
    }

    bool same=false;
    int u=move,px=x,py=y;
    for (int i=0; i<6; i++) {
        px-=dx[u&3]; py-=dy[u&3];
        if (!(px>=0&&py>=0&&px<h&&py<w)) break;
        if (px==x&&py==y) same=true;
        u>>=2;
    }
    if (!same&&mp[x][y]!='.') valt+=mp[x][y]-'0';

    if (valt<0&&x==h-1&&y==w-1) valt=1;
    //printf("%d %d: %d\n",x,y,valt);
    return dp[move][waste][x][y]=valt;
}

int main() {
    scanf("%d%d%d",&h,&w,&k);
    for (int i=0; i<h; i++) cin>>mp[i];
    memset(dp, -1, sizeof(dp));
    int res=dfs(0,0,0,0)-1;
    printf("%d\n",res<0?0:res);
}