Editorial for Hai quân xe


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n,a[333][333],row[333],col[333],ans;

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            scanf("%d",a[i]+j), row[i]+=a[i][j], col[j]+=a[i][j];
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++)
        {
            int mxI=-(1<<29),mxJ=mxI;
            for (int k=1;k<=n;k++)
            {
                int vI=col[k]-a[i][k]*2-a[j][k];
                int vJ=col[k]-a[i][k]-a[j][k]*2;
                ans=max(ans,row[i]+row[j]+mxI+vJ);
                ans=max(ans,row[i]+row[j]+mxJ+vI);
                ans=max(ans,row[i]+row[j]+col[k]-a[i][k]*2-a[j][k]*2);
                ans=max(ans,col[i]+col[j]+row[k]-a[k][i]*2-a[k][j]*2);
                mxJ=max(mxJ,vJ);
                mxI=max(mxI,vI);
            }
        }

    cout << ans << endl;
}

Code mẫu của ladpro98

program c11rooks;
uses    math;
const   maxn=303;
        fi='';
var     a:array[1..maxn,1..maxn] of longint;
        row,col,s1,s2:array[1..maxn] of longint;
        n,res:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                for j:=1 to n do read(inp,a[i,j]);
                readln(inp);
        end;
        close(inp);
end;

procedure init;
var     i,j:longint;
begin
        res:=low(longint);
        for i:=1 to n do
        begin
                row[i]:=0;
                for j:=1 to n do
                inc(row[i],a[i,j]);
        end;
        for j:=1 to n do
        begin
                col[j]:=0;
                for i:=1 to n do
                inc(col[j],a[i,j]);
        end;
end;

procedure process;
var     i,j,k,t,max1,max2:longint;
begin
        for i:=1 to n do
        begin
                for k:=1 to n-1 do
                for j:=k+1 to n do
                res:=max(res,row[i]+col[k]+col[j]-2*a[i,k]-2*a[i,j]);
                for j:=i+1 to n do
                begin
                        t:=row[i]+row[j];
                        for k:=1 to n do
                        begin
                                res:=max(res,t+col[k]-2*a[i,k]-2*a[j,k]);
                                s1[k]:=col[k]-2*a[i,k]-a[j,k];
                                s2[k]:=col[k]-a[i,k]-2*a[j,k];
                        end;
                        max1:=s1[1];max2:=s2[1];
                        for k:=2 to n do
                        begin
                                res:=max(res,t+s2[k]+max1);
                                res:=max(res,t+s1[k]+max2);
                                max1:=max(max1,s1[k]);
                                max2:=max(max2,s2[k]);
                        end;
                end;
        end;
end;

begin
        input;
        init;
        process;
        write(res);
end.

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 333;

int n, a[MN][MN];
int row[MN], col[MN], best[2][MN][MN], save[2][MN][MN], cc[MN][MN], rr[MN][MN];

int main() {
    while (scanf("%d", &n) == 1) {
        memset(row, 0, sizeof row);
        memset(col, 0, sizeof col);

        FOR(i,1,n) FOR(j,1,n) {
            scanf("%d", &a[i][j]);
            row[i] += a[i][j];
            col[j] += a[i][j];
        }

        FOR(i,1,n) FOR(j,1,n) {
            cc[i][j] = col[i] + col[j];
            rr[i][j] = row[i] + row[j];
        }

        int res = 0;
        // Same row
        FOR(i,1,n) {
            FOR(j1,1,n) FOR(j2,j1+1,n) {
                res = max(res, cc[j1][j2] + row[i] - 2*(a[i][j1] + a[i][j2]));
            }
        }

        // Same column
        FOR(j,1,n) {
            FOR(i1,1,n) FOR(i2,i1+1,n) {
                res = max(res, rr[i1][i2] + col[j] - 2*(a[i1][j] + a[i2][j]));
            }
        }

        // Different row, different column
        int now;
        FOR(i1,1,n) FOR(i2,1,n) if (i1 != i2) {
            best[0][i1][i2] = best[1][i1][i2] - 1000111000;
            int t = rr[i1][i2];
            FOR(j,1,n) {
                now = col[j] - 2*a[i2][j] - a[i1][j] + t;
                if (now > best[0][i1][i2]) {
                    best[0][i1][i2] = now;
                    save[0][i1][i2] = j;
                }
                else if (now > best[1][i1][i2]) {
                    best[1][i1][i2] = now;
                    save[1][i1][i2] = j;
                }
            }
        }

        FOR(i1,1,n) FOR(i2,1,n) if (i1 != i2)
        FOR(j1,1,n) {
            if (j1 == save[0][i1][i2])
                 res = max(res, col[j1] - 2*a[i1][j1] - a[i2][j1] + best[1][i1][i2]);
            else res = max(res, col[j1] - 2*a[i1][j1] - a[i2][j1] + best[0][i1][i2]);
        }
        cout << res << endl;
    }
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) {
  stringstream ss;
  if (p >= 0)
    ss << fixed << setprecision(p);
  ss << a;
  T r;
  ss >> r;
  return r;
}
template<class T> T gcd(T a, T b) {
  T r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
template<class T> T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template<class T> T sqr(T x) {
  return x * x;
}
template<class T> T cube(T x) {
  return x * x * x;
}
template<class T> int getbit(T s, int i) {
  return (s >> i) & 1;
}
template<class T> T onbit(T s, int i) {
  return s | (T(1) << i);
}
template<class T> T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template<class T> int cntbit(T s) {
  return s == 0 ? 0 : cntbit(s >> 1) + (s & 1);
}

typedef pair<int, int> II;

const double PI = acos(-1.0);
const double eps = 1e-3;

const int dr[] = { -1, 0, +1, 0 };
const int dc[] = { 0, +1, 0, -1 };

const int inf = (int) 1e9 + 5;
const ll linf = (ll) 1e16 + 5;
const ll mod = (ll) 1e9 + 7;

#define maxn 305

int n, a[maxn][maxn], sumr[maxn], sumc[maxn], A[maxn], B[maxn];

int cal(int c[],int d[]){
    int vt = -1, MAX = -1, res = 0;
    For(i, 1, n) if(c[i] > MAX){
        MAX = c[i];
        vt = i;
    }

    res = MAX;
    MAX = -1;
    For(i, 1, n) if(d[i] > MAX && i != vt){
        MAX = d[i];
    }
    res += MAX;
    return res;
}

int main() {
//  freopen("in.txt", "r", stdin);

    ms(sumr, 0); ms(sumc, 0);

    cin >> n;
    For(i, 1, n) For(j, 1, n){
        scanf("%d", &a[i][j]);
        sumr[i] += a[i][j];
        sumc[j] += a[i][j];
    }

    int res = 0;
    For(i, 1, n) For(j, i + 1, n){
        int ret = 0;
        ret += sumr[i] + sumr[j];
        for(int k = 1; k <= n; k++){
            A[k] = sumc[k] - a[i][k] - 2 * a[j][k];
            B[k] = sumc[k] - 2 * a[i][k] - a[j][k];
        }

        ret += max(cal(A, B), cal(B, A));
        res = max(res, ret);
    }

    For(i, 1, n){
        int ret = sumr[i];
        for(int k = 1; k <= n; k++){
            A[k] = sumc[k] - 2 * a[i][k];
        }
        ret += cal(A, A);
        res = max(res, ret);
    }

    For(i, 1, n){
        int ret = sumc[i];
        for(int k = 1; k <= n; k++){
            A[k] = sumr[k] - 2 * a[k][i];
        }
        ret += cal(A, A);
        res = max(res, ret);
    }

    cout << res;
//  cout << clock() << endl;
    return 0;
}

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   350
int a[MAX][MAX];
int r[MAX];
int c[MAX];
int n,b;
void init(void)
{
     int i,j;
     scanf("%d",&n);
     for (i=1;i<=n;i=i+1)
         for (j=1;j<=n;j=j+1)
             {
              scanf("%d",&a[i][j]);
              r[i]+=a[i][j];
              c[j]+=a[i][j];
             }
}
int max(int x,int y)
{
    int i,cx,cy,mx,my;
    mx=-32000;
    my=-32000;
    for (i=1;i<=n;i=i+1)
        if (c[i]-2*a[x][i]-a[y][i]>mx)
           {
            mx=c[i]-2*a[x][i]-a[y][i];
            cx=i;
           }
    for (i=1;i<=n;i=i+1)
        if (c[i]-2*a[y][i]-a[x][i]>my)
           {
            my=c[i]-2*a[y][i]-a[x][i];
            cy=i;
           }
    if (cx!=cy) return (mx+my+r[x]+r[y]);
    int cx1,cy1,mx1,my1;
    mx1=-32000;    
    my1=-32000;
    for (i=1;i<=n;i=i+1)
        if ((i!=cx) && (c[i]-2*a[x][i]-a[y][i]>mx1))
           {
            mx1=c[i]-2*a[x][i]-a[y][i];
            cx1=i;
           }
    for (i=1;i<=n;i=i+1)
        if ((i!=cy) && (c[i]-2*a[y][i]-a[x][i]>my1))
           {
            my1=c[i]-2*a[y][i]-a[x][i];
            cy1=i;
           }
    if (mx1+my>my1+mx) return (mx1+my+r[x]+r[y]);
    return (my1+mx+r[x]+r[y]);
}
void process(void)
{
     b=-32000;
     int i,j,k;
     for (i=1;i<n;i=i+1)
         for (j=i+1;j<=n;j=j+1)
             {
              k=max(i,j);              
              if (k>b) b=k; 
             }
     for (i=1;i<=n;i=i+1)
         for (j=1;j<n;j=j+1)
             for  (k=j+1;k<=n;k=k+1)
                  {
                   if (r[i]+c[j]+c[k]-2*a[i][j]-2*a[i][k]>b) b=r[i]+c[j]+c[k]-2*a[i][j]-2*a[i][k];
                   if (c[i]+r[j]+r[k]-2*a[j][i]-2*a[k][i]>b) b=c[i]+r[j]+r[k]-2*a[j][i]-2*a[k][i];
                  }
     printf("%d",b);
}
int main(void)
{
    init();
    process();   
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.