NDCCARD – spoj

05/03/2017 by Leave a Comment

Đề bài:

Thuật toán:

  • Dùng mảng f[i] đánh dấu giá trị lớn nhất <= i trong dãy A.
  • Vậy nên các cặp 3 số là a[i], a[j], f[m-a[i]-a[j]].
  • Chú ý đề bài cho dãy A đôi một khác nhau nhé.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int oo = 500001;
const int MAXN = 10001;
int i, j, n, m, a[MAXN], tmp, res, f[oo];
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    tmp = 0;
    for (int i = a[1]; i <= m; i++) {
        if ((tmp < n) && (i >= a[tmp+1])) tmp++;
        f[i] = a[tmp];
    }
    for (int i = 1; i<= n-2; i++) {
        for (int j = i+1; j <= n-1; j++) {
            tmp = m - a[i] - a[j];
            if (tmp < 1) continue;
            tmp = f[tmp];
            if (tmp <= a[j]) continue;
            res = max(res, a[i] + a[j] + tmp);
        }
    }
    cout << res;
    return 0;
}
CONST fin='';
     fout='';
VAR res, i, j, n, m, x, min: longint;
    a, ok: array[1..1000000] of longint;
    f: text;
BEGIN
  Assign(f,fin);
  Reset(f);
  Readln(f,n,m);
  min:=maxlongint-1;
  For i:=1 to n do
    Begin
      Read(f,a[i]);
      ok[a[i]]:=a[i];
      If a[i]<min then min:=a[i];
    End;
  Close(f);
  For i:=min+1 to  1000000 do
    If ok[i]=0 then ok[i]:=ok[i-1];
  res:=0;
  For i:=1 to n-1 do
    For j:=i+1 to n do
      Begin
        x:=m-a[i]-a[j];
        If x>0 then
          Begin
            If (ok[x]<>a[i]) and (ok[x]<>a[j]) and (ok[i]<>0) then
              If a[i]+a[j]+ok[x]>res then res:=a[i]+a[j]+ok[x];
          End;
      End;
  Assign(f,fout);
  Rewrite(f);
  Writeln(f,res);
  Close(f);
END.
Chủ đề: SPOJ
Khuyên dùng

 

Speak Your Mind

*