akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;

int main(void)
{
    IOS
    int n; cin >> n;
    vector<vector<int>> v;

    REP(i,n) {
        vector<int> v2(n-1);
        REP(j,n-1) {
            cin >> v2[j];
            v2[j]--;
        }
        v.emplace_back(v2);
    }

    int ans = 0;
    vector<int> cnt(n,0);
    set<pair<int,int>> q;
    
    auto next = [&](int i) {
        if (cnt[i] == n-1) return;
        int j = v[i][cnt[i]];
        //cerr << i << " " << j << endl;
        if (cnt[j] == n-1) return;
        if (v[j][cnt[j]] == i) {
            if (i > j) swap(i,j);
            q.emplace(make_pair(i,j));
        }
    };

    REP(i,n) {
        next(i);
    }

    while (!q.empty())
    {
        ans++;
        set<pair<int,int>> q2(q);
        q.clear();
        for(auto x : q2) {
            cnt[x.first]++;
            cnt[x.second]++;
        }
        for(auto x : q2) {
            next(x.first);
            next(x.second);
        }

    }
    
    REP(i,n) if (cnt[i] != n-1) ans = -1;
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

  int n;
  cin >> n;
  vector<int> stones(n);
  vector<int> dp(n);
  for (int i = 0; i < n; i++) {
    cin >> stones[i];
  }
  dp[0] = 0;
  dp[1] = abs(stones[0] - stones[1]);
  for (int i = 2; i < n; i++) {
    dp[i] = min(dp[i - 1] + abs(stones[i] - stones[i - 1]), dp[i - 2] + abs(stones[i] - stones[i - 2]));
  }
  cout << dp[n - 1] << endl;

	return 0;
}


Measured memory_bytes: 3972
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_H 60
#define MAX_W 60
#define INF 1e9
 
int H,W,N,ix,iy,ox,oy;
bool wall[MAX_H][MAX_W][4],a[MAX_H][MAX_W][4];
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
 
struct P{
  int x,y;
  P(int x,int y) : x(x),y(y) {}
};
 
inline bool inField(int x,int y){
  return (0 <= x && x < W && 0 <= y && y < H);
}
 
int bfs(){
  int d[MAX_H][MAX_W];
  for(int i = 0 ; i < H ; i++){
    for(int j = 0 ; j < W ; j++){
      d[i][j] = INF;
    }
  }
  d[iy][ix] = 0;
  queue<P> Q;
  Q.push(P(ix,iy));
  queue<int> step;
  step.push(0);
 
  while(!Q.empty()){
    P p = Q.front(); Q.pop();
    int s = step.front(); step.pop();
    int x = p.x, y = p.y;
    if(x == ox && y == oy){ return d[oy][ox]; }
    for(int i = 0 ; i < 4 ; i++){
      int nx = x + dx[i], ny = y + dy[i];
      if(wall[y][x][i]){ continue; }
      if(!inField(nx,ny)){ continue; }
      if(d[y][x]+1 < d[ny][nx]){
        d[ny][nx] = d[y][x]+1;
        Q.push(P(nx,ny));
        step.push(s+1);
      }
    }
  }
  return -1;
}
 
int main(){
  cin >> W >> H >> N;
  for(int i = 0 ; i < N ; i++){
    int sx,sy,dx,dy;
    cin >> sx >> sy >> dx >> dy;
    if(sx > dx){ swap(sx,dx); }
    if(sy > dy){ swap(sy,dy); }
    bool t = false,y = false;
    if(sx != dx){ y = true; }
    if(sy != dy){ t = true; }
    if(y){
      for(int j = sx ; j < dx ; j++){
        for(int k = sy ; k <= dy ; k++){
          if(k-1 >= 0){
            wall[k-1][j][3] = true;
            a[k-1][j][3] = true;
          }
          wall[k][j][1] = true;
          a[k][j][1] = true;
        }
      }
    }
    if(t){
      for(int j = sx ; j <= dx ; j++){
        for(int k = sy ; k < dy ; k++){
          if(j-1 >= 0){
            wall[k][j-1][2] = true;
            a[k][j-1][2] = true;
          }
          wall[k][j][0] = true;
          a[k][j][0] = true;
        }
      }
    }
  }
  int res = 0;
  cin >> ix >> iy >> ox >> oy;
  int dist = bfs();
  for(int x = 0 ; x <= W+1 ; x++){
    for(int y = 0 ; y <= H+1 ; y++){
      int xx = x-1,yy = y;
      if(xx >= 0){ wall[yy][xx][2] = wall[y][x][0] = true; }
      res = max(res,bfs()-dist);
      if(xx >= 0){
        wall[yy][xx][2] = a[yy][xx][2];
        wall[y][x][0] = a[y][x][0];
      }
    }
  }
  for(int x = 0 ; x <= W+1 ; x++){
    for(int y = 0 ; y <= H+1 ; y++){
      int xx = x,yy = y-1;
      if(yy >= 0){ wall[yy][xx][3] = wall[y][x][1] = true; }
      res = max(res,bfs()-dist);
      if(yy >= 0){
        wall[yy][xx][3] = a[yy][xx][3];
        wall[y][x][1] = a[y][x][1];
      }
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 1260
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    # 最大値 + 1を設定
    INF = N + 1
    A.sort()
    B.sort()
    C.sort()
    
    # True - ok - ng - False
    def is_ok(mid: int, b: int):
        # 判定する条件
        if mid < 0:
            return True
        elif mid >= N:
            return False
        return A[mid] < b
    
    # False - ng - ok - True
    def is_ok2(mid: int, b: int):
        # 判定する条件
        if mid < 0:
            return False
        elif mid >= N:
            return True
        return C[mid] > b

    def binSearch(ok: int, ng: int, b: int):
        #print(ok, ng)
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid, b):
                ok = mid
            else:
                ng = mid
            #print(ok, ng)
        return ok

    def binSearch2(ok: int, ng: int, b: int):
        #print(ok, ng)
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok2(mid, b):
                ok = mid
            else:
                ng = mid
            #print(ok, ng)
        return ok
    
    sum = 0
    for b in B:
        a = binSearch(-1, INF, b) - 0 + 1
        c = N - 1 - binSearch2(INF, -1, b) + 1
        sum += a * c
        #print(b, "->", a, c)
    print(sum)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 25568
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if (a + b == c + d)
        cout << "Balanced" << endl;
    else if (a + b > c + d)
        cout << "Left" << endl;
    else
        cout << "Right" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <iomanip>

int main()
{
    int n, k;
    std::cin >> n >> k;
    std::vector<double> p(n);
    for (int i = 0; i < n; i++)
    {
        std::cin >> p[i];
    }
    std::vector<double> s(n + 1);
    
    for (int i = 0; i < n; i++)
    {
        double tmp = p[i];
        p[i] = 0;
        for (int j = 1; j <= tmp; j++)
        {
            p[i] += j / tmp;
        }
    }
    

    for (int i = 0; i < n; i++)
    {
        s[i + 1] = s[i] + p[i];
    }

    double sum_max = 0;
    for (int i = 0; i < n - k + 1; i++)
    {
        double sum = s[i + k] - s[i];
        if (sum_max < sum)
        {
            sum_max = sum;
        }
    }

    std::cout << std::fixed << std::setprecision(12) << sum_max << std::endl;

    return 0;
}

Measured memory_bytes: 6480
#include<stdio.h>

int main(void)
{
    int i=0;
    double d;
    int count[8]={0};

    while(scanf("%lf",&d)!=EOF){
        if(i%2){
            if(1.1<=d) count[1]++;
            if(0.6<=d&&d<1.1) count[3]++;
            if(0.2<=d&&d<0.6) count[5]++;
            if(d<0.2) count[7]++;
        } else {
            if(1.1<=d) count[0]++;
            if(0.6<=d&&d<1.1) count[2]++;
            if(0.2<=d&&d<0.6) count[4]++;
            if(d<0.2) count[6]++;
        }
        i++;
    }
    for(i=0;i<8;i++){
        printf("%d",count[i]);
        if(i%2) puts("");
        else printf(" ");
    }
    return 0;
}

Measured memory_bytes: 640
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
constexpr int MOD=1000000007;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;

lint segdata[(1<<19)-1];

lint neutral(){
    return 0; //単位元
}
lint calc(lint a,lint b){
    return a+b; //演算
}
void seginit(){
    rep(i,(1<<19)-1) segdata[i]=neutral();
}
void update(lint i,lint x){ // i番目の値をxに更新
    i+=(1<<18)-1;
    segdata[i]=x;
    while(i>0){
        i=(i-1)/2;
        segdata[i]=calc(segdata[i*2+1],segdata[i*2+2]);
    }
}
lint seg(lint a,lint b,lint k,lint l,lint r){
    if(r<=a || b<=l) return neutral();
    if(a<=l && r<=b) return segdata[k];
    else{
        lint left=seg(a,b,k*2+1,l,(l+r)/2);
        lint right=seg(a,b,k*2+2,(l+r)/2,r);
        return calc(left,right);
    }
}
lint query(lint a,lint b){
    if(a>b) return 0;
    return seg(a,b+1,0,0,1<<18); //a~b(閉区間）の範囲での演算
}

int main(void){
    int N;
    cin >> N;
    rep(i,N){
        int A;
        cin >> A;
        update(i,A);
    }
    lint ans=LINF;
    rep(i,N+1) ans=min(ans,abs(query(0,i-1)-query(i,N-1)));
    cout << ans << endl;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
const int MOD=1000000007;
int main(){
    int x,y,z,k;
    cin>>x>>y>>z>>k;
    vector<int64_t> A(x),B(y),C(z);
    map<tuple<int,int,int>,int> p;
    rep(i,x) cin>>A[i];
    rep(i,y) cin>>B[i];
    rep(i,z) cin>>C[i];
    all(A),all(B),all(C);
    Re(A),Re(B),Re(C);
    priority_queue <tuple<int64_t,int,int,int>> ppq;
    queue <int64_t> pq;
    ppq.push(make_tuple(A[0]+B[0]+C[0],0,0,0));
    p[make_tuple(0,0,0)]++;
    int a=0,b=0,c=0;
    rep(i,k){
        int64_t t,q,w,e;
        tie(t,q,w,e) = ppq.top();
        ppq.pop();
        //cout<<t<<" "<<q<<" "<<w<<" "<<e<<endl;
        if(q+1<x && p[make_tuple(q+1,w,e)]==0){
           // cout<<"P1"<<endl;
            p[make_tuple(q+1,w,e)]++;
            ppq.push(make_tuple(A[q+1]+B[w]+C[e],q+1,w,e));
        }
        if(w+1<y && p[make_tuple(q,w+1,e)]==0){
            //cout<<"P2"<<endl;
            p[make_tuple(q,w+1,e)]++;
            ppq.push(make_tuple(A[q]+B[w+1]+C[e],q,w+1,e));
        }
        if(e+1<z && p[make_tuple(q,w,e+1)]==0){
            //cout<<"P3"<<endl;
            p[make_tuple(q,w,e+1)]++;
            ppq.push(make_tuple(A[q]+B[w]+C[e+1],q,w,e+1));
        }
        cout<<t<<endl;
        pq.push(t);

    }
    /*
    rep(i,k){
        cout<<pq.front()<<endl;
        pq.pop();
    }
    */
}

Measured memory_bytes: 896
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>

using namespace std;

int main() {
	int N; cin >> N;
	int* a = new int[N];
	int* b = new int[N];
	int* c = new int[N];

	for (int i = 0; i < N; i++) {
		cin >> a[i];
		if (i == 0) {
			b[i] = a[i];
		}
		else {
			b[i] = max(b[i - 1], a[i]);
		}
	}
	for (int i = N-1; i >= 0; i--) {
		if (i == N - 1) {
			c[i] = a[i];
		}
		else {
			c[i] = max(c[i + 1], a[i]);
		}
	}

	for (int i = 0; i < N; i++) {
		if (i == 0) {
			cout << c[i + 1] << endl;
		}
		else if (i == N - 1) {
			cout << b[i - 1] << endl;
		}
		else {
			cout << max(b[i - 1], c[i + 1]) << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3968
import sys
input = sys.stdin.readline
    
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
    
ans = 0
for i in range(n):
  if a[i] <= b[i]:
    ans += a[i]
    b[i] -= a[i]
    if a[i + 1] <= b[i]:
      ans += a[i + 1]
      a[i + 1] = 0
    else:
      ans += b[i]
      a[i + 1] -= b[i]
  else:
    ans += b[i] 
    
print(ans)


Measured memory_bytes: 19228
#include <bits/stdc++.h>
using namespace std;

int main() {
    int s; cin >> s;
    s *= 4;
    vector<int> vs;
    for(int i = 1; i <= s; ++i) {
        if(s % i != 0) continue;
        vs.push_back(i);
    }
    const int n = vs.size();
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            for(int k = 0; k < n; ++k) {
                const int w = vs[i], x = vs[j], y = vs[k];
                if(s % (w * x * y) != 0) continue;
                const int z = s / w / x / y;
                const int a = (w - x + 1) / 2, b = (w + x - 1) / 2;
                const int c = (y - z + 1) / 2, d = (y + z - 1) / 2;
                if(a <= 0 || b <= 0 || c <= 0 || d <= 0) continue;
                ans += s == (b + a) * (b - a + 1) * (d + c) * (d - c + 1);
            }
        }
    }

    cout << ans << endl;
}



Measured memory_bytes: 3148
s = str(input())
a = [1 if i == 'R' else - 1 for i in s] + [0]
ans = [0] * len(s)

lhigh, llow, rlow, rhigh = 0, 0, 0, 0
for i in range(len(s)):
    if a[i + 1] + 2 == a[i]: #1,-1
        llow = i
        rlow = i + 1 
    elif (a[i + 1] - 2 == a[i]) or (i == len(s) - 1):
        rhigh = i
        lcnt, rcnt = llow - lhigh + 1, rhigh - rlow + 1
        ans[llow] = lcnt // 2 + rcnt // 2 + lcnt % 2
        ans[rlow] = lcnt // 2 + rcnt // 2 + rcnt % 2
        lhigh = i + 1
print(*ans)


Measured memory_bytes: 49568
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(17) << res << endl;
 
int main() {
    ll n, k;
    cin >> n >> k;
    if ((n % k) == 0) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <numeric>
#define rep(i,n) for (int i = 0;i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
int INF = 1e9;


int main(){
	vector<string> s(3);cin >> s[0] >> s[1] >> s[2];
	int ind = 0;
	while(true){
		if(s[ind].size()==0) {
			char ans = 'A'+ind;
			cout << ans << endl;
			return 0;
		}
		int next = s[ind][0] - 'a';
		s[ind] = s[ind].substr(1,s[ind].size()-1);
		ind = next;
	}
} 


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define rep(i,n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main() {
  int N, K;
  cin >> N >> K;

  vector<int> c(N+1, 0);
  int a;
  rep(i, N) {
    cin >> a;
    c[a]++;
  }

  vector<int> balls;
  rep(i, c.size()) {
    if (c[i] > 0) balls.push_back(c[i]);
  }

  std::sort(balls.begin(), balls.end());

  int sum = 0;
  int loop = balls.size() - K;
  rep(i, loop) {
    sum += balls[i];
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 2168
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
20 3
5 10 15
'''

def solve(l,K):
	n = len(l)
	l += [l[0] + K]
	l = sorted(l)
	maxx = 0
	for i in range(n):
		maxx = max(maxx,l[i+1]-l[i])
	return K - maxx
	

K,N = list(map(int, stdin.readline().rstrip().split()))
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l,K)
print(ans)


Measured memory_bytes: 74280
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 9223372036854775807
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<P> Graph;  

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n,m;
  cin >> n >> m;
  
  int a[m],b[m],c[m];
  REP(i,m){
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
    c[i] *= -1; //最短経路問題に
  }
  
  ll score[n];
  REP(i,n) score[i] = INF;
  
  score[0] = 0;
  
  //BellmanFord法、負閉路がないと仮定してチェック
  REP(i,n-1){
    REP(j,m){
      if(score[a[j]] == INF) continue;
      if(score[b[j]] > score[a[j]]+c[j]) score[b[j]] = score[a[j]]+c[j];
    }
  }
  
  //負閉路チェック
  //この時点で負閉路が無い場合は，最適解が得られているため更新はおきない.
  //負閉路の最大の長さn回分ループして，更新された場所と，そこを経由する部分は負閉路を含む
  bool f[n];
  REP(i,n) f[i] = false;
  
  REP(i,n){
    REP(j,m){
      if(score[a[j]] == INF) continue;
      if(score[b[j]] > score[a[j]]+c[j]){
        score[b[j]] = score[a[j]]+c[j];
	    f[b[j]] = true; 
      }
      if(f[a[j]]) f[b[j]] = true;
    }
  }
  
  if(f[n-1])
    cout << "inf" << endl;
  else
    cout << -score[n-1] << endl;
        
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int i, n, a[300005];
long long sum1, sum2, rs, dp[2][300005];
multiset<int> S1, S2;

int main() {
  ios_base::sync_with_stdio(0);

  cin >> n;
  for(i = 1; i <= 3 * n; ++i) cin >> a[i];

  for(i = 1; i <= 3 * n; ++i) {
    if(i <= n) {
      dp[0][i] = dp[0][i - 1] + a[i];
      S1.insert(a[i]);
      continue;
    }

    S1.insert(a[i]); 
    dp[0][i] = dp[0][i - 1] + a[i] - (*S1.begin());
    S1.erase(S1.begin());
  }

  for(i = 3 * n; i; --i) {
    if(i > 2 * n) {
      dp[1][i] = dp[1][i + 1] + a[i];
      S2.insert(-a[i]);
      continue;
    }

    S2.insert(-a[i]);
    dp[1][i] = dp[1][i + 1] + a[i] + (*S2.begin());
    S2.erase(S2.begin());
  }

  for(i = 2 * n - 1; i > n; --i) dp[1][i] = min(dp[1][i], dp[1][i + 1]);

  rs = dp[0][n] - dp[1][n + 1];
  for(i = n + 1; i <= 2 * n; ++i) rs = max(rs, dp[0][i] - dp[1][i + 1]);

  cout << rs << '\n';

  return 0;
}

Measured memory_bytes: 15488
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, m, a, b, c[210005] = {}, d[666] = {}, z[666] = {}, o = 328;
    cin >> n >> m;
    for (int i = 0; i < 666; i++) d[i] = -1, z[i] = mod;
    for (int i = 1; i <= m; i++) c[i] = i, z[i / o] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a >> b;
        int e = d[(a - 1) / o];
        if (e == -1) e = c[a - 1];
        if (a / o == b / o) {
            if (d[a / o] != -1) for (int j = a / o * o; j < (a / o + 1) * o; j++) c[j] = e;
            d[a / o] = -1;
            z[a / o] = mod;
            for (int j = a; j <= b; j++) c[j] = e;
            for (int j = a / o * o; j < (a / o + 1) * o; j++) if (c[j]) z[a / o] = min(z[a / o], j - c[j]);
        } else {
            int u = a / o, v = b / o;
            if (d[u] != -1) for (int j = u * o; j < (u + 1) * o; j++) c[j] = d[u];
            if (d[v] != -1) for (int j = v * o; j < (v + 1) * o; j++) c[j] = d[v];
            d[u] = d[v] = -1;
            z[u] = z[v] = mod;
            for (int j = a; j < (u + 1) * o; j++) c[j] = e;
            for (int j = v * o; j <= b; j++) c[j] = e;
            for (int j = u * o; j < (u + 1) * o; j++) if (c[j]) z[u] = min(z[u], j - c[j]);
            for (int j = v * o; j < (v + 1) * o; j++) if (c[j]) z[v] = min(z[v], j - c[j]);
            for (int j = u + 1; j < v; j++) {
                d[j] = e;
                if (e) z[j] = j * o - e;
                else z[j] = mod;
            }
        }
        int y = mod;
        for (int j = 0; j < 666; j++) y = min(y, z[j]);
        //for (int j = 1; j <= m; j++) cout << c[j] << ' ' << d[j] << ' ' << z[j] << '\n';
        if (y == mod) cout << -1 << '\n';
        else cout << y + i << '\n';
    }
}


Measured memory_bytes: 4444
#include <iostream>
#include <map>
using namespace std;

int main() {
    int n, vi;
    cin >> n;
    map<int, int> even, odd;
    for (int i = 1; i <= n; i++) {
        cin >> vi;
        (i & 1 ? odd[vi] : even[vi])++;
    }

    int key_odd_max1, key_odd_max2, key_even_max1, key_even_max2;
    for (auto oddi : odd) {
        if (oddi.second > odd[key_odd_max1]) key_odd_max1 = oddi.first;
    }
    for (auto eveni : even) {
        if (eveni.second > even[key_even_max1]) key_even_max1 = eveni.first;
    }
    for (auto oddi : odd) {
        if (oddi.second > odd[key_odd_max2] && oddi.first != key_odd_max1) key_odd_max2 = oddi.first;
    }
    for (auto eveni : even) {
        if (eveni.second > even[key_even_max2] && eveni.first != key_even_max1) key_even_max2 = eveni.first;
    }

    int ans = n - (odd[key_odd_max1] + even[key_even_max1]);
    if (key_odd_max1 == key_even_max1) {
        ans = n - max(odd[key_odd_max1] + even[key_even_max2], odd[key_odd_max2] + even[key_even_max1]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define MOD (long long)(1e9 + 7)
using namespace std;

template <int mod>
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y)
      : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const {
    return ModInt(*this) += p;
  }
  ModInt operator-(const ModInt &p) const {
    return ModInt(*this) -= p;
  }
  ModInt operator*(const ModInt &p) const {
    return ModInt(*this) *= p;
  }
  ModInt operator/(const ModInt &p) const {
    return ModInt(*this) /= p;
  }
  bool operator==(const ModInt &p) const {
    return x == p.x;
  }
  bool operator!=(const ModInt &p) const {
    return x != p.x;
  }
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  ModInt pow(int64_t n) const {
    ModInt ans(1), mul(x);
    while(n) {
      if(n & 1) ans *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ans;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
  static int get_mod() { return mod; }
};

long long n;
vector<long long> c;

ModInt<MOD> solve();

int main() {
  cin >> n;
  c.resize(n);
  for(int i = 0; i < n; ++i) cin >> c[i];
  sort(c.begin(), c.end());

  cout << solve() << endl;
  return 0;
}

ModInt<MOD> solve() {
  ModInt<MOD> res = 0;
  for(int i = 0; i < n; ++i) {
    ModInt<MOD> two = 2, now = 0;
    if(n - i - 2 >= 0)
      now = two.pow(n - i - 2) * (n - i - 1);
    now += two.pow(n - i - 1);
    now *= two.pow(n + i);
    now *= c[i];
    res += now;
  }
  return res;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
#define zmrl(x) (int)((x).size())
#define pb push_back
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
const int mod = 1e9+7;

int fact[3030], inv[3030];

int comb(int n, int r) {
    return fact[n]*inv[n-r]%mod*inv[r]%mod;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin>>n;
    fact[0] = fact[1] = inv[0] = inv[1] = 1;
    for (int i=2; i<=3000; i++) {
        fact[i] = fact[i-1]*i%mod;
        inv[i] = -mod/i*inv[mod%i]%mod;
    }
    for (int i=2; i<=3000; i++) {
        inv[i] = inv[i-1]*((inv[i]+mod)%mod)%mod;
    }
    int res = 0;
    for (int i=1;; i++) {
        if (n-3*i < 0) break;
        res = (res + comb(n-2*i-1, n-3*i)) % mod;
    }
    cout << res << '\n';
    return 0;
}

Measured memory_bytes: 3696
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

bool isPrime(int n) {
    if (n == 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

void calc(int n) {
    auto ans = recurrence!"a[n-1] + 1"(1)
        .filter!(e => isPrime(e) && e % 5 == 1)
        .take(n);
    writeln(ans.map!text.join(' '));
}

void main() {
    int n; scan(n);
    calc(n);
}

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
using namespace std;

const int MOD     = 1000000000 + 7;
const int REV_MOD = 1000000000 + 5;
vector<int> factMod = vector<int>(100000+2);
vector<int> reverseMod = vector<int>(100000+2);
    
void prepareFactMod(){
    int N = factMod.size() - 1;
    long long res = 1;
    for(long long i=1; i<=N; i++){
        res = (res * i)%MOD;
        factMod[i] = (int)res;
    }
}

long long culcExp(long long root, int expnum){
    if(expnum == 1)return root;
    long long res = culcExp(root, expnum/2);
    
    if(expnum %2 == 1){
        return (((res*res)%MOD)*root)%MOD;
    }else{
        return (res * res)%MOD;
    }
}

void prepareReverseMod(){
    int N = reverseMod.size()-1;
    for(int i=1; i<=N; i++){
        reverseMod[i] = (int)culcExp(factMod[i], REV_MOD);
    }
}

int culcCombination(int n, int r){
    if(r > n){
        return 0;
    } else if(n == 0 || n == r || r == 0){
        return 1;
    }
    return (((factMod[n] * (long long)reverseMod[r]) % MOD) * (long long)reverseMod[n-r]) % MOD;
}

int main(void){
    int N=0, n=0, buf=0;
    cin >> N;
    vector<int> bucket = vector<int>(N+1, 0);
    
    for(int i=0; i<N+1; i++){
        cin >> buf;
        if(bucket[buf] >0){
            n = (N-i) + bucket[buf] -1;
            break;
        }
        bucket[buf] = i + 1;
    }
    
    prepareFactMod();
    prepareReverseMod();

    for(int i=0 ; i<N+1; i++){
        int res =  culcCombination(N+1, i+1) - culcCombination(n, i);
        cout << ((res>0) ? res : (res+MOD)) << endl;
    }
    
    return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

using P = pair<double, double>;

double dist(P a, P b)
{
    double x = a.first - b.first;
    double y = a.second - b.second;
    return sqrt(x * x + y * y);
}

double calcS(P A, P B, P C)
{
    double a = dist(A, C);
    double b = dist(A, B);
    double c = dist(B, C);
    double s = (a + b + c) / 2.0;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<P> p(3); //A,B,C
    for (int i = 0; i < 3; i++)
    {
        cin >> p[i].first >> p[i].second;
    }
    sort(ALL(p));
    double ans = 0;
    do
    {
        double S = calcS(p[0], p[1], p[2]);
        double ab = dist(p[0], p[1]);
        double bc = dist(p[1], p[2]);
        double ca = dist(p[2], p[0]);
        double ah = (double)2 * S / bc;
        double r = (double)2 * S / ((ab + bc + ca + (double)2 * ah));
        chmax(ans, r);
    } while (next_permutation(ALL(p)));
    cout << fixed;
    cout << setprecision(15) << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct _OMAZINAI_ { _OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } __omazinai_instance__;
#define INF (1LL<<61 + 1<<29)
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
typedef long long int ll;


int main() {
	int n;
	cin >> n;
	cout << n / 3 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  char str[1000];
  long a, b, c, d;
  
  fgets(str, sizeof(str), stdin);
  sscanf(str, "%ld %ld %ld", &a, &b, &c);
  
  d = c - a - b;
  if(d < 0){
    printf("%s\n", "No");
  }else if(4 * a * b < d * d){
	printf("%s\n", "Yes");
  }else{
    printf("%s\n", "No");
  }
  
  return 0;
}


Measured memory_bytes: 2112
use input::Input;

fn main() {
    let mut input = Input::new();

    let n: usize = input.parse();
    let mut k: usize = input.parse();
    let v = (0..n)
        .map(|_| input.parse::<usize>() - 1)
        .collect::<Vec<_>>();

    let mut cp = 0;
    let mut np = v[cp];
    for _ in 0..n {
        if k == 0 {
            println!("{}", cp + 1);
            return;
        }
        cp = np;
        np = v[cp];
        k -= 1;
    }

    let mut w = vec![false; n];
    let mut cnt = 0;
    while !w[np] {
        w[np] = true;
        cp = np;
        np = v[np];
        cnt += 1;
    }

    for _ in 0..k % cnt {
        cp = np;
        np = v[cp];
    }

    println!("{}", cp + 1);
}

#[allow(dead_code)]
pub mod input {
    use std::io::stdin;
    use std::str::{FromStr, SplitAsciiWhitespace};

    pub struct Input<'a>(SplitAsciiWhitespace<'a>);

    fn naive_read<'a>() -> SplitAsciiWhitespace<'a> {
        let mut s = Box::leak(Box::new(String::new()));
        stdin().read_line(&mut s).expect("failed to read");
        s.split_ascii_whitespace()
    }

    impl<'a> Input<'a> {
        pub fn new() -> Self {
            Self(naive_read())
        }
        pub fn read_line(&mut self) -> String {
            let mut s = String::new();
            stdin().read_line(&mut s).ok().expect("failed to read");
            s
        }
        pub fn parse<T: FromStr>(&mut self) -> T {
            let x = if let Some(x) = self.0.next() {
                x
            } else {
                self.0 = naive_read();
                self.0.next().expect("reached EOF")
            };
            x.parse().ok().expect("failed to parse")
        }
    }
}


Measured memory_bytes: 5184
import sys
input = sys.stdin.readline

class Unionfind:

    __slots__ = ['nodes','size']

    def __init__(self, n):
        self.nodes = list(range(n))
        self.size = [1]*n

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)

N,K,L = map(int,input().split())

uf1 = Unionfind(N)
uf2 = Unionfind(N)

for _ in range(K):
    p,q = map(int,input().split())
    p -= 1; q -= 1
    uf1.unite(p,q)

for _ in range(L):
    r,s = map(int,input().split())
    r -= 1; s -= 1
    uf2.unite(r,s)

keys = []
dic = {}

for node in range(N):
    key = (uf1.root(node),uf2.root(node))
    keys.append(key)
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))

Measured memory_bytes: 65820
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define endl '\n'
#define mod 1000000007
#define mod1 1000000009
#define line cout<<"----------------------"<<endl
#define mp make_pair
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define filein freopen("input.txt","r",stdin)
#define fileout freopen("output.txt","w",stdout)
using namespace std;
const ll   mx=200009;
ll  ara[mx];
ll  cnt[mx];
int  main()
{
    ll  n;
    cin>>n;
    for(ll  i=0;i<n;i++)
    {
        cin>>ara[i];
        cnt[ara[i]]++;
    }
    ll ans=0;
    for(ll  i=0;i<=n;i++)
    {
        ll  d=cnt[i];
        ans+=d*(d-1)/2;
    }
    for(ll  i=0;i<n;i++)
    {
        ll  d=cnt[ara[i]];
        ll  bad=d*(d-1)/2;
        d--;
        ll  jog=d*(d-1)/2;
        cout<<ans-bad+jog<<endl;
    }

}


Measured memory_bytes: 4736
using System;
class Program
{
    static void Main(string[] args)
    {
        string[] str = Console.ReadLine().Split(' ');
        int Sheep = int.Parse(str[0]);
        int Wolves = int.Parse(str[1]);
       
      
        if (Wolves < Sheep)
        {
            Console.WriteLine("safe");
        }
        else
        {
            Console.WriteLine("unsafe");
        }

    }
}

Measured memory_bytes: 27480
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();

    if (b % a == 0) {
      System.out.println(a + b);
    } else {
      System.out.println(b -a);
    }

  }
}


Measured memory_bytes: 21972
#include<iostream>
#include<algorithm>
#include <string>
#include<cstdio>
#include<stack>
#include<cstring>
#include<vector>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define D(n,retu) REP(i,n){cin>>retu[i];}

using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}

//------------------変数-----------------------//
ll n, k, a[300005], goukei = 0;
//-------------------関数----------------------//

int main() {
	cin >> n >> k;
	REP(i, n) { cin >> a[i]; }
	sort(a, a + n);
	if (a[n - 1] < k) { cout << "IMPOSSIBLE" << endl; return 0; }
	ll fir = a[0];
	ll yaku = 0;
	ll cou = 1;
	REP(i, n ) {
		yaku = gcd(yaku, a[i ] );
	}if (yaku == 0) { yaku = a[0]; }
	if (k%yaku == 0) { cout << "POSSIBLE" << endl; return 0; }
	cout << "IMPOSSIBLE" << endl; return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;

# define C continue;
# define R return

# define D double
# define I insert
# define ll long long
# define ld long double

# define ull unsigned long long
# define ui unsigned int

# define pb push_back
# define pf push_front

# define vi vector < int >
# define vc vector < char >
# define vs vector < string >
# define vb vector < bool >
# define vd vector < D >
# define vll vector < ll >
# define vull vector < ull >
# define vld vector < ld >
# define PQ priority_queue

# define vvi vector < vector < int > >
# define vvb vector < vector < bool > >
# define vvc vector < vector < char > >
# define vvll vector < vector < ll > >
# define vvd vector < vector < D > >
# define vvld vector < vector < ld > >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()
# define allcomp(v) v.begin() , v.end() , comp
# define allrevcomp(v) v.rbegin() , v.rend() , comp

# define pii pair < int , int >
# define pll pair < ll , ll >
# define pld pair < ld , ld >
# define pDD pair < D , D >

# define vpld vector < pld >
# define vpii vector < pii >
# define vpll vector < pll >
# define vpDD vector < pDD >

# define vvpii vector < vector < pii > >
# define F first
# define S second
# define mp make_pair

# define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))

# define pp(n) printf("%.10Lf",n);
# define line cout<<"\n";
# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);

string vow = "aeiou";
int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};

const int dx[] = { -1 , 0 , 0 , 1 } ;
const int dy[] = { 0 , -1 , 1 , 0 } ;

const ld pie = 3.1415926535897932384626 ;
const ll mod = 1e9 + 7 ;

/// Tip : If a and b are positive integers ; we may say - ceil (a/b) = 1 + floor ( (a-1)/b ) .

int h , n ;

vpii v ;
map < int  , ll > dp ;

void read()
{
    cin >> h >> n ;
    v.resize ( n ) ;

    for ( int i=0 ; i < n ; i ++ ) cin >> v[i].F >> v[i].S ;
}

bool comp ( pii a , pii b )
{
    ll lhs = a.F * b.S ;
    ll rhs = b.F * a.S ;

    if ( lhs == rhs )
        return false ;

    if ( lhs > rhs )
        return true ;

    return false ;
}

ll f ( int h )
{
    if ( h <= 0 )
        return 0LL ;

    if ( dp.count ( h ) )
        return dp[h] ;

    ll ret = 1e10 ;
    for ( auto j : v )
    {
        ret = min ( ret , f ( h - j.F ) + j.S ) ;
    }

    dp[h] = ret ;
    return ret ;
}

void solve ( int test_case )
{
    read() ;
    // sort ( allcomp ( v ) ) ;

    ll ans = f ( h ) ;
    cout << ans ;

    line
}

int main()
{fast
    int t = 1;
    // cin >> t;

    for ( int i=0 ; i < t ; i++ ) solve(i);
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<int>   vi;
typedef vector<long long> vll;
typedef vector<pair<int,int> > vii;
#define ll long long
#define pb push_back
#define mp  make_pair
#define ff first
#define ss second
#define pq priority_queue
#define sf(x) scanf("%d",&x)
int inf = (1e9) + 7;


set<int> dis;
int good(int i){
	while(i > 0){
		if(dis.count(i%10))
			return 0;
		i/=10;
	}	
	return 1;
}

int main(){



	int n;
	int k;

	cin >> n >> k;
	int aux;
	for (int i = 0; i < k; ++i)
	{
		sf(aux);
		dis.insert(aux);
	}


	int cont = n;
	while(!good(cont))
		cont++;
	printf("%d\n",cont );

}

Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    ArrayList<Integer> a = new ArrayList<Integer>(n);
    for (int i=0 ; i<n ; i++){
      a.add(sc.nextInt());
    }
    Collections.sort(a);
    double ans=a.get(0);
    for (int i=1 ; i<n ; i++){
      ans=(ans+a.get(i))/2;
    }
    
    System.out.println(ans);
  }
}

Measured memory_bytes: 23124
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
typedef long long ll;
using namespace std;
int R, C, K;
ll DP[3004][3004][4];
ll items[3004][3004];

int main() {
  INCANT;
  cin >> R >> C >> K;
  int r,c;
  ll v;
  rep(i, K) {
    cin >> r >> c >> v;
    r--;c--;
    items[r][c] = v;
  }
  rep(i, R) {
    rep(j, C) {
      for (int k=2; k>=0; k--) {
        DP[i][j][k+1] = max(DP[i][j][k]+items[i][j], DP[i][j][k+1]);
      }
      rep(k,4) {
        DP[i][j+1][k] = max(DP[i][j+1][k], DP[i][j][k]);
        DP[i+1][j][0] = max(DP[i+1][j][0], DP[i][j][k]);
      }
    }
  }
  ll MAX=0ll;
  rep(i, 4) MAX=max(MAX, DP[R-1][C-1][i]);
  cout << MAX << endl;
  return 0;
}

Measured memory_bytes: 355608
#include <bits/stdc++.h>
using namespace std;

using str = string;
using ss = stringstream;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n,l;
    cin>>n>>l;

    vector<str> s;
    for(int i=0;i<n;i++)
    {
        str is;
        cin>>is;
        s.push_back(is);
    }

    sort(s.begin(),s.end());

    for(int i=0;i<n;i++)cout<<s[i];

    cout<<"\n";

    return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

void io_set() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

int main(){
    IOS
    //io_set();
    string s;
    cin>>s;
    ll i,n=s.size();
    unordered_map<ll,ll>m;
    for(i=0;i<n;i++){
        m[s[i]]++;
    }
    for(auto it:m){
        if(it.second&1){
            cout<<"No\n";
            return 0;
        }
    }
    cout<<"Yes\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cout << #x << ": " << x << endl
#define repn(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) for(int i = 0; i < (a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'

ll w[405], s[405], dp[405][405];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> w[i];
		s[i] = s[i - 1] + w[i];
	}
	for(int l = 2; l <= n; l++){
		for(int i = 1; i <= n - l + 1; i++){
			int j = i + l - 1;
			dp[i][j] = 1e18;
			for(int k = i; k < j; k++){
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
			}
		}
	}	
	cout << dp[1][n] << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#include <cmath>

using namespace std;

int main(){

	int h, w, a, b, tmp;

	cin>> h >> w >> a >> b;

	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			tmp=0;
			if(j<a) tmp++;
			if(i<b) tmp++;

			if(tmp==1) cout<< "0";
			else cout<< "1";
		}
		cout<< endl;
	}

}

Measured memory_bytes: 1280
#include <stdio.h>
#include <stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;
Node treeMinimum(Node x){
  while(x->left!=NIL)x=x->left;
  return x;
}

Node treeMaximum(Node x){
  while(x->right!=NIL)x=x->right;
  return x;
}

Node treeSearch(Node u,int x){
  while(u!= NIL && x != u->key){
    if(x < u->key)u=u->left;
    else u=u->right;
  }
  return u;
}

Node treeSuccessor(Node x){
  if(x->right != NIL)return treeMinimum(x->right);
  Node y = x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y;
  Node x;
  if(z->left == NIL || z->right == NIL)y=z;
  else y= treeSuccessor(z);
  if(y->left != NIL)x=y->left;
  else x=y->right;
  if(x!=NIL)x->parent=y->parent;
  if(y->parent==NIL)root=x;
  else{
    if(y==y->parent->left)y->parent->left=x;
    else y->parent->right=x;
  }
  if(y!=z)z->key=y->key;
  free(y);
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key)x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL)root=z;
  else {
    if(z->key < y->key)y->left=z;
    else y->right=z;
  }
}

void inorder(Node u){
  if(u==NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char c[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", c);
    if(c[0]=='f'){
      scanf("%d",&x);
      Node t = treeSearch(root,x);
      if(t!=NIL)printf("yes\n");
      else printf("no\n");
    }
    else if ( c[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( c[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if(c[0]== 'd'){
      scanf("%d",&x);
      treeDelete(treeSearch(root,x));
    }
    else;
  }

  return 0;
}



Measured memory_bytes: 20520
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pb push_back
#define ub upper_bound
#define lb upper_bound
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
 
using ll = long long;
const ll INF = LLONG_MAX/4 - 100;
ll mod = 1e9 + 7;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;

class fact {
public:
	int fmod = 1e9+7;
	vector<int> fac, inv;
	fact (int n, int Mod = 1e9+7) {
		fmod = Mod;
		fac = vector<int>(n,0);
		inv = vector<int>(n,0);
		fac[0] = 1; for (int i = 1; i < n; i++) fac[i] = fac[i-1] * i % fmod;
		for (int i = 0;i < n;i++) inv[i] = fact::POW(fac[i],fmod-2);
	}
	ll nCr(ll n, ll r) {return (fac[n] * inv[r] % fmod) * inv[n-r] % fmod;}
	ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%fmod;}a = a * a%fmod; b >>= 1;}return c;}
};
 
template <class T = ll> T in() {T x; cin >> x; return (x);}
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
void EMP(int x) {cout<<"!!!"<<x<<"!!!"<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return a * b / GCD(a, b);}
ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%mod;}a = a * a%mod; b >>= 1;}return c;}
void PRI(ll n) {bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) {a[i] = 1LL;}for (int i = 2; i < n + 1LL; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}
bool isSqrt(ll a) {return pow(sqrt(a),2) == a ? 1 : 0;}
void YesNo(bool a) {if (a) cout << "Yes"; else cout << "No"; cout << endl;}
void yesno(bool a) {if (a) cout << "yes"; else cout << "no"; cout << endl;}
void YESNO(bool a) {if (a) cout << "YES"; else cout << "NO"; cout << endl;}

int yosan[450][450];
int dp[450][450];

bool solve() {
    REP (i,450) REP (j,450) {yosan[i][j] = INF;dp[i][j] = INF;}
    yosan[0][0] = 0; dp[0][0] = 0;
    int n,ma,mb; cin >> n >> ma >> mb;
    REP (i,n) {
        int a,b,c; cin >> a >> b >> c;
        REP (j,450) {
            REP (k,450) {
                if (j+a >= 450 || k+b >= 450) continue;
                chmin(dp[j+a][k+b],yosan[j][k]+c);
            }
        }
        REP (j,450) {
            REP (k,450) {
                yosan[j][k] = dp[j][k];
            }
        }
    }
    int ans = INF;
    REP (i,450) {
        REP (j,450) {
            if (!i || !j) continue;
            if (i * mb == j * ma) {
                chmin(ans,dp[i][j]);
            }
        }
    }
    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
}


Measured memory_bytes: 3456