Submission #416527

#	Time	Username	Problem	Language	Result	Execution time	Memory
416527		MarcoMeijer	Nafta (COI15_nafta)	C++14	34 / 100	294 ms	55140 KiB

nafta

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second

const int INF	= 1e9;
const int MX	= 3000;
const int N	= 1<<20;
const int MOD	= 1e9+7;

int r, s;
char gr[MX][MX];
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};

// grid
bool inside(int x, int y) {
  return x>=0&&y>=0&&x<r&&y<s;
}
bool isOil(int x, int y) {
  if(!inside(x,y)) return 0;
  return gr[x][y] != '.';
}

// DSU
int ra[N], p[N], minx[N], maxx[N], sm[N];
void builddsu() {
  RE(x,r) RE(y,s) {
    int i=x+y*r;
    ra[i]=0, p[i]=i, minx[i]=y, maxx[i]=y, sm[i]=0;
    if(gr[x][y] != '.') sm[i]=gr[x][y]-'0';
  }
}
int getSet(int i) {return i==p[i] ? i : p[i]=getSet(p[i]);}
void unionSet(int i, int j) {
  i = getSet(i); j = getSet(j);
  if(i == j) return;
  sm[i] = sm[j] = sm[i]+sm[j];
  minx[i] = minx[j] = min(minx[i], minx[j]);
  maxx[i] = maxx[j] = max(maxx[i], maxx[j]);
  if(ra[i] > ra[j]) {
    p[j]=i;
  } else {
    p[i]=j;
    if(ra[i] == ra[j]) ra[j]++;
  }
}

// daq dp
int cost[MX][MX];
int dp[MX][MX];
void daq(int x, int l, int r, int al, int ar) {
  if(r < l) return;
  int m=(l+r)/2;

  int bsti=al,bstAns=0;
  REP(i,al,ar+1) {
    if(i+1 > m) continue;
    int nAns = dp[i][x-1] + cost[i+1][m];
    if(nAns > bstAns) {
      bstAns = nAns;
      bsti=i;
    }
  }
  dp[m][x] = bstAns;

  daq(x,l,m-1,al,bsti);
  daq(x,m+1,r,bsti,ar);
}

int main() {
  cin>>r>>s;
  RE(i,r) RE(j,s) cin>>gr[i][j];

  builddsu();
  RE(x,r) RE(y,s) RE(d,4) {
    int nx=x+dx[d];
    int ny=y+dy[d];
    if(!isOil(x,y) || !isOil(nx,ny)) continue;
    unionSet(x+y*r, nx+ny*r);
  }

  RE(i,r*s) {
    if(p[i] != i) continue;
    if(!sm[i]) continue;
    cost[minx[i]  ][maxx[i]  ] += sm[i];
    cost[maxx[i]+1][maxx[i]+1] -= sm[i];
  }


  RE(i,s) RE(j,s) {
    if(i)
      cost[i][j] += cost[i-1][j];
    if(j)
      cost[i][j] += cost[i][j-1];
    if(i && j)
      cost[i][j] -= cost[i-1][j-1];
  }

  RE(i,s) {
    dp[i][0] = 0;
    RE(j,i+1) dp[i][0] = max(dp[i][0], cost[j][i]);
  }

  REP(i,1,s) {
    daq(i,0,s-1,0,s-1);
  }

  RE(i,s) cout<<dp[s-1][i]<<endl;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 66