akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll n;
  cin >> n;
  if (n % 10 == 9 || n / 10 == 9) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 3604
#include <stdio.h>
#define N 100000
#define M 50000
int binary (int, int, int *,int *);

int main (){
  int m,n,a,b,A[N],B[M],ans,i;
  
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%d",&a);
    A[i]=a;
  }
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&b);
    B[i]=b;
  }

  ans =  binary(m,n,B,A);

  printf("%d\n",ans);

  return 0;
}

int binary (int m,int n,int B[],int A[]){
  int i,left,right,center;
  int count = 0;
  for(i=0;i<n;i++){
    left=0;
    right=m;

    while(left<right){
    center=(left+right)/2;
    if(A[center]==B[i]){
      count++;
      break;
    }
    else if(B[i]<A[center])
      right = center;
    else left = center+1;
    }
    
    
  }
  
  return count;
}



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

typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;
#define global sdajklasdnkl
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)(a.size())
#define debug(a) cout << #a << " = " << a << endl;
#define FILL(a, value) memset(a, value, sizeof a)

const double PI = acos(-1.0);
const int base = 1000 * 1000 * 1000;
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
const int mod = 1000 * 1000 * 1000 + 7;
const int half = (mod + 1) / 2;
int mult(int x , int y)
{
	return (x * (LL)y ) % mod;
}
int add(int a , int b)
{
	return a + b >= mod ? a + b - mod : a + b;
}
int sub(int a , int b)
{
	return a - b < 0 ? a - b + mod : a - b;
}
int a[100005];
int pref[100005];
int fact[100005] , inv[100005];
int power(int x , int y)
{
    int ans = 1;
    while(y)
    {
        if(y & 1)
        {
            ans = mult(ans , x);
        }
        x = mult(x , x);
        y >>= 1;
    }
    return ans;
}
int sum(int l , int r)
{
    return sub(pref[r] , (l ? pref[l - 1] : 0));
}
int main()
{
        //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      // freopen("in.txt" , "r" , stdin);
       //vector<int> permut;
      // int n = 3;
      
      fact[0] = 1;
      inv[0] = 1;
      for(int i = 1; i <= 100004; i++)	
      {
        fact[i] = mult(fact[i - 1] , i);
        inv[i] = power(fact[i] , mod - 2);
      }
      int n;
            cin >> n;
      for(int i = 0; i < n; i++)
       		cin >> a[i];
       pref[0] = a[0];
       for(int i = 1; i < n; i++)
            pref[i] = add(pref[i - 1] , a[i]);
       int ans = mult(sum(0 , n - 1) , fact[n]);
       int Sum = 0;
       for(int len = 1; len < n; len++)
       {
            if(len <= n - len - 1)
            {
                  Sum = add(Sum , sum(len , n - len - 1));
            }
            if(len > n - len - 1)
            {
                Sum = sub(Sum , sum(n - len , len - 1));
            }
           // cout << Sum << endl;
       	    int s1 = mult(Sum , mult(2 , mult(inv[len + 2] , mult(fact[n] , fact[len]))));
       	    int s2 = mult(inv[len + 1] , mult(fact[n] , fact[len]));
       	    //cout << s1 << endl;
            ans = add(ans , s1);

            ans = add(ans , mult(sum(0 , len - 1) , s2));
            ans = add(ans , mult(sum(n - len , n - 1) , s2));
            
           // cout << ans << endl;
       }
	cout << ans;
}




Measured memory_bytes: 1792
use std::collections::HashSet;

fn main() {
  let n: usize = read();
  let vec: Vec<usize> = reads(n);

  let mut svec = vec.clone();
  svec.sort();
  let sset = svec.chunks(2).map(|c|c[0]).collect::<HashSet<_>>();

  let set = vec.chunks(2).map(|c|c[0]).collect::<HashSet<_>>();

  let ans = set.difference(&sset).count();
  println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
  let mut buf = String::new();
  std::io::stdin().read_line(&mut buf).ok();
  buf.trim().parse::<T>().ok().unwrap()
}

fn reads<T: std::str::FromStr>(n: usize) -> Vec<T> {
  let mut vec: Vec<T> = vec![];
  for _ in 0 .. n {
    vec.push(read());
  }
  vec
}


Measured memory_bytes: 10492
# -*- coding: utf-8 -*-

def main():
    n = int(input())
    num_list = list(map(int, input().split()))

    counter = 0

    for i in range(n):
        if(num_list[i] == i+1):
            continue
        else:
            counter += 1

    if(counter <= 2):
        print("YES")
    else:
        print(("NO"))


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
try:
    from math import gcd # >=Python 3.5
except:
    from fractions import gcd # <Python 3.5 (AtCoder : 3.4)

def solve(X, xs):
    xs = list(xs) + [X]
    xs.sort()
    zs = [x - xs[0] for x in xs]

    for z in zs:
        if z == 0:
            D = z
        else:
            D = gcd(D, z)
    return D

def test():
    print(solve(13, [16 + 3 * 102485 * i for i in range(10**5)]))

if __name__=='__main__':
    N, X = map(int, input().split())
    xs = map(int, input().split())

    print(solve(X, xs))


Measured memory_bytes: 16324
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main() {
  int h, w; cin >> h >> w;
  vector<vector<int>> g(10, vector<int>(10));
  rep(i, 10) rep(j, 10) cin >> g[i][j];
  vector<vector<int>> a(h, vector<int>(w));
  rep(i, h) rep(j, w) cin >> a[i][j];

  rep(k, 10) rep(i, 10) rep(j, 10) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  int ans = 0;
  rep(i, h) rep(j, w) {
    if (a[i][j] != -1) ans += g[a[i][j]][1];
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
package main

import (
	"bufio"
	"os"
	"strings"
	"sort"
	"fmt"
)

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	// get stg input
	a := nextLine()
	b := nextLine()

	// already same value
	if a == b {
		fmt.Println("Yes")
		return
	}
	// never be same because they contain different characters
	if sortAsString(a) != sortAsString(b) {
		fmt.Println("No")
		return
	}
	// try
	size := len(a)
	for i := 0; i < size; i ++ {
		b = b[size-1:size] + b[0:size-1]
		if a == b {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
	return
}

func sortAsString(p string) string {
	list := strings.Split(p, "")
	sort.Strings(list)
	return strings.Join(list, "")
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main(void){
  string N;
  cin >> N;

  /*まず初めに左2つの数字または右2つの数字が同じかの判定をする．
    つまり，aabcのパターンか，abccのパターンである．
    上記に当てはまるとき，中央2つの数字に着目し，等しければ題意を満たす．．
    aabcのとき，a=bであればaaac，
    abccのとき，b=cであればacccである．
   */
  
  if(N[0] == N[1] || N[2] == N[3]) //左2つの数字が同じ or 右2つの数字が同じ
    if(N[1] == N[2]) //中央2つの数字が同じ
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  else
    cout << "No" << endl;
  

  return 0;
}


Measured memory_bytes: 256
import java.util.*
import java.math.*

fun main(args: Array<String>) {

//    var (A,B,C,D) = readLine()!!.split(" ").map { it.toLong() }
    var N = readLine()!!.toInt()
//    val D = readLine()!!.split(" ").map { it.toLong() }
    val H = readLine()!!.split(" ").map { it.toLong() }.toLongArray()

    var ans = "Yes"
    var max = H[0]
    for (h in H.drop(1)) {
        if (max-h >= 2) ans = "No"
        if (max < h) max = h
    }
    println(ans)

//    println("%.9f".format(ans))
}


Measured memory_bytes: 64112
def main():
    n = int(input())
    A = list(map(int, input().split()))

    sum_a = sum(A)

    d = dict()

    for a in A:
        d[a] = d.get(a, 0) + 1

    for _ in range(int(input())):
        b, c = map(int, input().split())
        if d.get(b, 0) != 0:

            temp = d[b]         
            d[b] -= temp
            d[c] = d.get(c, 0) + temp

            sum_a += (c - b) * temp
        print(sum_a)
        
main()


Measured memory_bytes: 93488
#include <iostream>
using namespace std;
int main() {
	string s;
	cin >> s;
	int counter[26];
	for(int i=0;i<26;i++){
		counter[i] = 0;
	}
	for(int i=0;i<s.size();i++){
		counter[s[i]-'a']++;
	}
	string ans = "None";
	string t = "abcdefghijklmnopqrstuvwxyz";
	for(int i=0;i<26;i++){
		if(counter[i]==0){
			ans = t[i];
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
using namespace std;

int main(){
    
    string str,x;
    int m,h;
    
    while(1) {
        
        cin >> str >> m;
        
        if (str == "-") break;
        
        for (int i = 0; i < m ; i ++) {
        
            cin >> h;
        
            x = str.substr(0,h);
        
            str.erase(0,h);
        
            str += x;
        
        }
        
        cout << str << endl;
    
    
    }
    
    return 0;
    
    
    
}


Measured memory_bytes: 3140
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds; 

#define int long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define f first
#define s second
#define sz(x) (int)x.size()
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.14159265358979323846

typedef long long ll;
typedef long double ld; 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> oset;

// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

const int mod = 1e9 + 7;
const int inf = 9e18;
const int N = 1e5 + 5;

int i,n,m,k,a[N],b[N],c[N],d[N],ans[N],vis[N],mark[N],nodes;
set<int> g[N],comp;

void dfs(int v){
    ++nodes;
    comp.insert(v);
    vis[v]=1;
    for(int u:g[v]){
        if(vis[u])
            continue;
        dfs(u);
    }
}

void solve(){
    cin>>n>>m>>k;
    for(i=1;i<=m;++i){
        cin>>a[i]>>b[i];
        g[a[i]].insert(b[i]);
        g[b[i]].insert(a[i]);
    }
    for(i=1;i<=n;++i){
        if(!vis[i]){
            nodes=0;
            comp.clear();
            dfs(i);
            for(int j:comp){
                ans[j]=nodes-1-sz(g[j]);
                mark[j]=i;
            }
        }
    }
    for(i=1;i<=k;++i){
        cin>>c[i]>>d[i];
        if(mark[c[i]]==mark[d[i]] && g[c[i]].find(d[i])==g[c[i]].end()){
            --ans[c[i]];
            --ans[d[i]];
        }
    }
    for(i=1;i<=n;++i){
        cout<<ans[i]<<" ";
    }
}

signed main(){
    fastio;
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 25088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N; cin >> N; int H[N]; int Max = 0;
  int ans = 0;
  for(int i = 0; i < N; i++){
    cin >> H[i];
    if(H[i] >= Max) ans++;
    Max = max(Max, H[i]);
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
a, b, c, d, e, k = [int(input()) for _ in range(6)]

l = []

l.append(abs(a - b))
l.append(abs(a - c))
l.append(abs(a - d))
l.append(abs(a - e))
l.append(abs(b - c))
l.append(abs(b - d))
l.append(abs(b - e))
l.append(abs(c - d))
l.append(abs(c - e))

for x in l:
    if x > k:
        print(':(')
        exit()

print('Yay!')

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

#define all(A) (A).begin(), (A).end()
#define sz(A) int((A).size())

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector <ll> a(n), b(n), c(n - 1);
  for (ll& elem: a) cin >> elem;
  for (ll& elem: b) cin >> elem;
  for (ll& elem: c) cin >> elem;
  ll ans = accumulate(all(b), 0LL);
  for (int i = 0; i + 1 < n; i++) {
    if (a[i] + 1 == a[i + 1]) ans += c[a[i] - 1];
  }
  cout << ans << '\n';
  return (0);
}

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

int main() {
	// your code goes here
	long long a, b;
	cin >> a >> b;
	long long ans = a * b;
	if(a < b){swap(a, b);}
	
	int r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  
  ans /= b;
  cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		while (true) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int C = sc.nextInt();
			if (A == 0) break;
			int N = sc.nextInt();
			int[][] fail = new int[N][3];
			int[] ans = new int[301];
			Arrays.fill(ans, 2);
			int fi = 0;
			for (int i = 0; i < N; ++i) {
				int I = sc.nextInt();
				int J = sc.nextInt();
				int K = sc.nextInt();
				int R = sc.nextInt();
				if (R == 1) {
					ans[I] = ans[J] = ans[K] = 1;
				} else {
					fail[fi][0] = I;
					fail[fi][1] = J;
					fail[fi][2] = K;
					++fi;
				}
			}
			for (int i = 0; i < fi; ++i) {
				int cand = 0;
				for (int j = 0; j < 3; ++j) {
					if (ans[fail[i][j]] != 1) cand += (1 << j);
				}
				if (Integer.bitCount(cand) == 1) {
					ans[fail[i][Integer.numberOfTrailingZeros(cand)]] = 0;
				}
			}
			for (int i = 1; i <= A + B + C; ++i) {
				System.out.println(ans[i]);
			}
		}
	}
}

Measured memory_bytes: 12000
// C - 4-adjacent
#include <bits/stdc++.h>
using namespace std;

int in(){int x;cin>>x;return x;}
// int in(){int x;scanf("%d",&x);return x;}

int main(){
	int N = in();
	int count1 = 0, count4 = 0, not_exist2 = 1;
	while(N--){
		switch (in()%4){
		case 2: not_exist2 = 0; break;
		case 0: count4++; break;
		default: count1++;
		}
	}
	puts(count1 <= count4 + not_exist2? "Yes":"No");
}

Measured memory_bytes: 256
import java.util.*;
import java.util.stream.Collectors;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    int total = 0;
    int ans = Integer.MAX_VALUE;
    ;
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < N; i++) {
      list.add(sc.nextInt());
      min = Math.min(min, list.get(i));
      max = Math.max(max, list.get(i));
    }
    for (int i = min; i <= max; i++) {
      total = 0;
      for (int j = 0; j < N; j++) {
        total += Math.pow(i - list.get(j), 2);
      }
      ans = Math.min(ans, total);
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1001001001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> list(n - 1);
    vector<int> G[n];
    vector<map<int, int>> ans(n);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        list[i].first = a;
        list[i].second = b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int maxi = 0;
    for (int i = 0; i < n; i++)
    {
        maxi = max(maxi, int(G[i].size()));
    }
    vector<bool> seen(n);
    seen[0] = true;
    queue<pair<int, int>> qe; // 頂点，親とどの色でつながっているか
    qe.push(make_pair(0, 0));
    while (!qe.empty())
    {
        auto nows = qe.front();
        qe.pop();
        int now = nows.first;
        int use = nows.second;
        int color = 1;
        for (auto next : G[now])
        {
            if (seen[next])
            {
                continue;
            }
            if (color == use)
            {
                ++color;
            }
            ans[now][next] = color;
            // cout << now << ':' << next << ':' << color << endl;
            qe.push(make_pair(next, color));
            seen[next] = true;
            ++color;
        }
    }
    cout << maxi << endl;
    for (auto l : list)
    {
        cout << ans[l.first][l.second] << endl;
    }
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
};

Measured memory_bytes: 18848
#include <bits/stdc++.h>
using namespace std;
//________
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)
#define show(x) cerr << #x << ':' << (x) << endl
#define outl(x) cout << (x) << '\n'
#define FAST() cin.tie(0), ios::sync_with_stdio(false)

typedef long long ll;
typedef pair<int,int> Pii;
template<class A, class B>inline bool chmax(A &a, B b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, B b){return b<a ? a=b,1 : 0;}
inline bool inside(int y, int x, int H, int W){return(y>=0 && x>=0 && y<H && x<W);}
const int INF = 1 << 29;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
#define Size 1000011
//________


signed main()
{
    FAST();
    int N, M;
    cin >> N >> M;

    outl( (N+M+1) / 2);
}



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

#define FOR(i, j, k) for(int i = j; i < k; i++)
#define REP(i, j) FOR(i, 0, j)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

template <class T> bool chmax(T &a, const T &b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool chmin(T &a, const T &b) {
    if(b < a) {
        a = b;
        return 1;
    }
    return 0;
}

template <typename T> istream &operator>>(istream &is, vector<T> &vec) {
    for(T &x : vec)
        is >> x;
    return is;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    string s;
    cin >> s;

    map<char, int> m;

    for(char c : s) {
        m[c]++;
    }

    for(pair<char, int> p : m) {
        if(p.second != 2) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}


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

#define mp          make_pair
#define pb          push_back
#define ff          first
#define ss          second
#define ii          pair<int,int>
#define mod         (int)1e9+7
#define inf         1e18
#define max_v       200005

typedef long long int lli;
typedef long double ld;

#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int A[100005];
int dp[100005];

int rec(int i,int n)
{
    if(i==n)
        return 0;
    if(dp[i]!=-1)
        return dp[i];
    int cost=abs(A[i]-A[i+1])+rec(i+1,n);
    if(i+2<=n)
        cost=min(cost,abs(A[i]-A[i+2])+rec(i+2,n));

    return dp[i]=cost;
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
    }
    memset(dp,-1,sizeof(dp));
    cout<<rec(1,n)<<endl;
    return ;
}

int main()
{
    fio

    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
 
    int t;
    t=1;
//    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 10628
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define ub upper_bound
#define lb lower_bound
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;



struct Edge{
  int src;int dst;double wei;
  Edge(int s=0,int d=0,double w=0):src(s),dst(d),wei(w){}
};

using Graph = vector<vector<Edge>>;

pair<vector<double>,vector<int>> Dij(Graph&g,int s){
    using state = pair<double,int>;//テ」ツつウテ」ツつケテ」ツδ暗」ツ?ョテァツキツ湘・ツ陳古」ツ??」ツ?ゥテ」ツ?禿」ツ?凝」ツつ嘉ィツヲツ凝」ツ?ヲテ」ツ??」ツつ凝」ツ?ョテ」ツ??
    priority_queue<state,vector<state>,greater<state>> pq;
    vector<int> from(g.size());
    vector<double> dis(g.size(),INF);
    dis[s]=0;
    pq.push(state(0,s));
    while(!pq.empty()){
      double d=pq.top().first;
      int v=pq.top().second;
      pq.pop();
      if(dis[v]<d)continue;
      rep(i,g[v].size()){
        Edge &e=g[v][i];
        if(dis[e.dst]>dis[v]+e.wei){
          dis[e.dst]=dis[v]+e.wei;
          pq.push(state(dis[e.dst],e.dst));
          from[e.dst]=v;
        }
      }
    }
    return mp(dis,from);
}

signed main(){
    int n;
    while(cin>>n,n){
    vector<pair<int,pair<int,int>>> B(n);
  //  vector<int> B(n),X(n),Y(n);
  //  rep(i,n)cin>>B[i]>>X[i]>>Y[i];
    rep(i,n){
      int a,b,c;
      cin>>a>>b>>c;
      B[i]=mp(a,mp(b,c));
    }
    sort(B.begin(),B.end());
    Graph g(n);
    rep(i,n)rep(j,n){
      if(i==j)continue;
      //double x=abs(X[i]-X[j]);
      //double y=abs(Y[i]-Y[j]);
      double x=abs(B[i].sec.fir-B[j].sec.fir);
      double y=abs(B[j].sec.sec-B[i].sec.sec);

      if(x*x+y*y<=2500.0){
        double dst=pow(x*x+y*y,0.5);
        g[i].emplace_back(i,j,dst);
        g[j].emplace_back(j,i,dst);
      }
    }

    int m;
    cin>>m;
    vector<int> S(m),G(m);
    rep(i,m)cin>>S[i]>>G[i];
    rep(i,m){
      auto ans=Dij(g,S[i]-1);
      //rep(i,n)cout<<ans.fir[i]<<' '<<ans.sec[i]<<endl;
      if(ans.fir[G[i]-1]==INF){
        cout<<"NA"<<endl;
        continue;
      }
      stack<int> path;
      for(int j=G[i]-1;;j=ans.sec[j]){
        path.push(j);
        if(j==S[i]-1)break;
      }
      while(!path.empty()){
        cout<<path.top()+1;
        if(path.size()!=1)cout<<' ';
        path.pop();
      }
      cout<<endl;
    }

  }

  return 0;
}

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

using namespace std;
int n,i,j,d;
long long a[3005];
long long dp[3005][3005];
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    for(d=0;d<=n;d++)
    {
        for(i=1;i+d<=n;i++)
        {
            if(d==0)
                dp[i][i]=a[i];
            else
            {
                dp[i][i+d]=max(a[i]-dp[i+1][i+d], a[i+d]-dp[i][i+d-1]);
            }
        }
    }

    cout<<dp[1][n];
    return 0;
}


Measured memory_bytes: 49736
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr ll mod998=998244353;

int K;
string S;
int main(){
	cin>>K>>S;
	if(S.size()<=K){
		cout<<S<<endl;
	}
	else{
		for(int i=0;i<K;i++)cout<<S[i];
		cout<<"..."<<endl;
	}
}


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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

template <typename T>
void fin(T a)
{
  cout << a << endl;
  exit(0);
}

//実行部
void Main()
{
  ll k, a, b; cin >> k >> a >> b;
  if(k + 1 <= a||b - a <= 2)
  {
    fin(1 + k);
  }
  else
  {
    ll ans = a;
    k -= (a - 1);
    if(k % 2 == 1) ans++;
    ans -= a * (k / 2);
    ans += b * (k / 2);
    fin(ans);
  }
  
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}

/*
//test時
  g++ test.cpp -o test;./test
*/


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 100000;

int n;
vector<int> adj[MaxN + 1];

int dfs(int u, int fa)
{
	int w = 0;
	for (int v : adj[u])
		if (v != fa)
			w ^= dfs(v, u) + 1;
	return w;
}

int main()
{
	cin >> n;
	for (int i = 1; i < n; ++i)
	{
		int u = getint(), v = getint();
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cout << (dfs(1, 0) ? "Alice" : "Bob");
	cout << endl;

	return 0;
}

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

using namespace std;


#define MAXN 1000000
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int a, b;
  cin >> a >> b;
  string s;
  cin >> s;
  bool ans = true;
  for (int i = 0; i < s.size(); ++i) {
    if (i==a) continue;
    ans &= isdigit(s[i]);
  }
  ans &= s[a]=='-';
  ans &= s.size()==a+b+1;
  cout << (ans ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll                long long int
#define ld                long double
#define pb                push_back
#define pf                push_front
#define ppb               pop_back
#define ppf               pop_front
#define sz                size()
#define pi                acos(-1.0)
#define mod               1000000007
#define F                 first
#define S                 second
#define C                 continue
#define G                 goto done
#define maxe              max_element
#define mine              min_element
#define min3(a,b,c)       min(a,min(b,c))
#define max3(a,b,c)       max(a,max(b,c))
#define min4(a,b,c,d)     min(a,min(b,min(c,d)))
#define max4(a,b,c,d)     max(a,max(b,max(c,d)))
#define mem(a,b)          memset(a,b,sizeof(a))
#define all(a)            (a).begin(),(a).end()
#define gcd(a,b)          __gcd(a,b)
#define lcm(a,b)          ((a)*((b)/gcd(a,b)))
#define case(a)           cout<<"Case "<<(a)<<": "
#define point(a)          fixed<<setprecision(a)
#define get(a)            for(auto &x:a) cin>>x
#define print(a)          for(auto x:a) cout<<x<<" "; cout<<endl
#define see(x)            cout<<#x<<" = "<<x<<endl
#define uniq(a)           sort(all(a)); (a).erase(unique((a).begin(),(a).end()),(a).end())
#define big(a)            transform((a).begin(),(a).end(),(a).begin(),::toupper)
#define small(a)          transform((a).begin(),(a).end(),(a).begin(),::tolower)
#define ischar(a)         (('a'<=a&&a<='z')('A'<=a&&a<='Z'))
#define isvowel(a)        (a=='a'||a=='e'||a=='i'||a=='o'||a=='u'||a=='A'||a=='E'||a=='I'||a=='O'||a=='U')
#define fast              ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define tc                int test; cin>>test; while(test--)
using namespace std;
int main()
{
    int n; cin>>n;
    if(n==1) cout<<0;
    else cout<<1;
}




















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

def main():
    N = int(input())
    keta = 1
    ans = ""
    while 1:
        x = N % (26**keta) // (26**(keta-1))
        if x == 0:
            x = 26
        ans = chr(ord("a") + (x-1)) + ans
        N -= x * (26**(keta-1))
        keta += 1
        if N == 0:
            break
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9188
# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def dfs(A):
    # 再代入のため、グローバル宣言
    global ans
    
    # N桁なら計算
    if len(A) == N:
        score = 0
        for a, b, c, d in buff:
            if A[b-1] - A[a-1] == c:
                score += d
        ans = max(ans, score)
        return
    
    A.append(A[-1])
    # 再帰
    while A[-1] <= M:
        # コピーを渡す
        dfs(A[:])
        A[-1] += 1


# main
N, M, Q = map(int, input().split())
buff = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
dfs([1])

print(ans)

Measured memory_bytes: 9160
#include <bits/stdc++.h>
using namespace std;
#define data_type long long

int main()
{
  string str;
  cin>>str;
  data_type sum=0;
  for(auto i:str)
   sum+=i-'0';
  cout<<(sum%9==0?"Yes":"No")<<endl;
    return 0;

}


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

#include<math.h>

//#define pi 3.14159265358979323846
#define pi acos(-1.0)
using namespace std;

int main()
{



    int r;

    cin>>r;

    double a=2*pi*r;

    printf("%.2lf",a);//cout<<a<<endl;

    return 0;


}


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

int main() {
    long long h,w;
    cin>>h>>w;
    if (h==1 || w == 1) {
        cout << 1<<endl;
    }
    else if (h%2==0||w%2==0){
        cout << h*w/2<<endl;
    }
    else {
        cout << (h*w+1)/2<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
#define D  double
typedef pair<D,int>T;
int N;
int X[1111],Y[1111],R[1111];
D dist[1111];
D INF=1e10;
D EPS=1e-9;
 
int table2[1111][1111];
D table[1111][1111];
 
signed main(){
 
    cin>>X[0]>>Y[0]>>X[1]>>Y[1];
    cin>>N;
    rep(i,N)cin>>X[i+2]>>Y[i+2]>>R[i+2];
    N+=2;
 
    rep(i,N)rep(j,N){
        table2[i][j]=(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]);
        table[i][j]=sqrt(1.0*table2[i][j]);
    }
 
    fill_n(dist,1111,INF);
    dist[0]=0;
    priority_queue<T,vector<T>,greater<T>>que;
    que.push(make_pair(0,0));
    while(que.size()){
        D d;
        int idx;
        tie(d,idx)=que.top();
        que.pop();

        if(dist[idx]<d) continue;

        rep(i,N){
            int foo=table2[i][idx];
            int bar=R[i]+R[idx];
            D cost=d;
            if(foo>bar*bar) cost+=sqrt(1.0*foo)-bar;
            if(dist[i]>EPS+cost){
                dist[i]=cost;
                que.push(T(dist[i],i));
            }
        }
    }
    printf("%.20f\n",dist[1]);
    return 0;
}

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

int main() {
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;

  s1[0] += 'A' - 'a';
  s2[0] += 'A' - 'a';
  s3[0] += 'A' - 'a';

  cout << s1[0] << s2[0] << s3[0] << endl;
}

Measured memory_bytes: 256
import scala.io.StdIn.readInt

object Main extends App {
  val s = readInt

  val (h, baseMin) = (s / (60 * 60), s % (60 * 60))
  val (m, sec) = (baseMin / 60, baseMin % 60)

  println(s"$h:$m:$sec")

}



Measured memory_bytes: 43740
#include<iostream>
#include <array>
#include <vector>
#include <algorithm>
#include "math.h"
using namespace std;

int main() {
  int A, B, AB, AN, BN;
  cin >> A >> B >> AB >> AN >> BN;
  if (AN > BN) {
    std::swap(AN, BN);
    std::swap(A, B);
  }
  std::vector<int> plans;
  plans.push_back(BN * 2 * AB);
  plans.push_back(A * AN + B * BN);
  if (AN != BN) {
    plans.push_back(AN * 2 * AB + (BN - AN) * B);
    // plans.push_back((AN - (BN - AN)) * A + (BN - AN) * AB * 2);
  }
  int min = *std::min_element(plans.begin(), plans.end());
  std::cout << min;
  return 0;
}

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

#define ld			long double
#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define MOD         1000000007
#define sd(t) 		scanf("%d",&(t))
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define hii 		cout << "hii" << endl
#define okay 		cout << "okay" << endl
#define hey 		cout << "hey" << endl

template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; } 
 
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
}

clock_t time_p=clock();
void starboy1299()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

const int N = 2e5+5;
int arr[N];
int dp[105][N];
int n, k;
int price[N];
int f(int idx, int wt){
	if(idx==n or wt==0){
		return 0;
	}
	if(dp[idx][wt]!=-1) return dp[idx][wt];
	int ans = 0;
	if(arr[idx] <= wt)
		ans = max(ans, price[idx] + f(idx+1, wt-arr[idx]));
  
	ans = max(ans, f(idx+1, wt));
	
	return dp[idx][wt] = ans;
}

void solve()
{
	cin >> n >> k;
	memset(dp, -1, sizeof(dp));
	rep(i, 0, n){
		cin >> arr[i] >> price[i];
	}

	cout << f(0, k) << endl;
}			 

int32_t main(){
	fast();
    int t = 1;
    // cin>> t;
    while(t--){
    	solve();
    }
	starboy1299();
}




Measured memory_bytes: 164608
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



h, w, n = LI()
A = []
for a, b in LIR(n):
    for i, j in product((1, 0, -1), (1, 0, -1)):
        if 2 <= a + i <= h - 1 and 2 <= b + j <= w - 1:
            A += [(a + i, b + j)]


ans = [0 for i in range(9)]
for k, v in Counter(A).items():
    ans[v - 1] += 1


print((h - 2) * (w - 2) - sum(ans))
for j in ans:
    print(j)

Measured memory_bytes: 166220
#include<bits/stdc++.h>
#define ll long long
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int main()
{
    fast_io
    ll i,j,n;
    cin>>n;
    ll a[n];
    ll cost=0,prev=0,ans;
    for(i=0; i<n; i++)
    {
        cin>>a[i];
        cost+=abs(prev-a[i]);
        prev=a[i];
    }
    cost+=abs(a[n-1]);
    prev=0;
    for(i=0; i<n; i++)
    {
        ans=cost;
        if(i==n-1)

            ans=ans-abs(a[i]-prev)-abs(a[i])+abs(a[i-1]);
        else
            ans=ans-abs(a[i]-prev)-abs(a[i+1]-a[i])+abs(a[i+1]-prev);
        prev=a[i];
        cout<<ans<<endl;

    }

    return 0;
}





Measured memory_bytes: 4444
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <utility>
#include <sstream>
#include <numeric>
#include <iterator>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
// #define ll long long
typedef long long ll;
typedef pair<int, int> P;

unsigned int len(unsigned int n)
{
    return n ? len(n/10)+1 : 0;
}

int main(int argc, const char * argv[]) {

  int n;
  cin >> n;
  vector< long > a(n);
  rep(i, n) cin >> a[i]; 
  // vector< double > a2(n, 1);
  long double sum_ = 0;
  rep(i, n){
     sum_ += 1.0 / a[i];
  }
  cout << (long double)(1.0 / sum_) << endl;
  return 0;
}


Measured memory_bytes: 888
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

int main(int argc, char* argv[]) {
  int N;
  cin >> N;

  vector<string> s(N);
  for (int i = 0; i < N; ++i)
    cin >> s[i];

  set<string> past;
  for (int i = 0; i < N; ++i) {
    past.insert(s[i]);
  }

  cout << past.size() << endl;


  return 0;
}

Measured memory_bytes: 25108
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rfor(i, a, b) for(int i = a; i < (int)b; i++)
#define all(ary) (ary).begin(), (ary).end()
#define debug(x) cerr << #x << ": " << x << '\n'
const long long INF = 1LL << 60;
const int MOD = 1000000007; // 1e9 + 7
using namespace std;
using vec = vector<int>;
using ll = long long;
template <class T = int> T in(){ T x; cin >> x; return (x);}
template <class T> inline bool chmin(T &a, T b) { if ( a > b ) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T &a, T b) { if ( a < b ) { a = b; return 1; } return 0; }
const int dy[4] = {-1, 0, 0, 1};
const int dx[4] = {0, -1, 1, 0};

ll N, K;
ll res = 0;
ll a, b, c;

int main(int argc, char *argv[]){
    cin >> N >> K;
    ll n = 0;
    // rfor(i, 1, N + 1) if(i % K == 0) n++;
    n = N / K;
    ll m = 0;
    rfor(i, 1, N + 1) if(i % K == K / 2) m++;
    res = n * n * n;
    if(K % 2 == 0) res += m * m * m;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
/***
**   AUTHOR::ASHUTOSH MOUDGIL
***/


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

#define pb push_back
#define mp make_pair
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define F first
#define S second
#define int long long
//#define ll long long
#define all(x) x.begin(),x.end()
#define rsort(x) sort(all(x)); reverse(all(x));
#define endl '\n'
#define vi vector<int>
#define vlli vector<long long>
#define pii pair<int,int>
#define mod 1000000007
#define LMAX 1e18
#define deb(x) cout<<#x<<" : "<<x<<endl;
#define PI 3.141592654
#define deb1(x) cout << #x <<"="<< x <<endl;
#define deb2(x,y) cout << #x <<"="<<x<<", "<<#y<<"="<<y <<endl;
#define deb3(x,y,z) cout << #x <<"="<<x<<", "<<#y<<"="<<y <<", "<<#z<<"="<<z<<endl;
#define deb4(x,y,z,a) cout << #x <<"="<<x<<", "<<#y<<"="<<y <<", "<<#z<<"="<<z<< ", "<<#a <<"="<<a << endl;
#define debarr(x) cout << #x<<"::"<<endl;for(int i : x){cout << i <<" ";} cout <<endl;

inline void add(int& a, int b){a = (a+b); if(a>=mod)a-=mod;}
inline void sub(int& a, int b){a = a-b; if(a<0)a+=mod;}
inline void mul(int& a, int b){a = (a*b)%mod;}

const int N = 3e4;
int n;
vi dp(N+1,0);

vector<pair<int,pair<int,int>>> arr;
bool cmp(pair<int,pair<int,int>> a , pair<int,pair<int,int>> b){
    return a.F+a.S.F < b.F+b.S.F;
}

void mymain(){
    cin >> n;
    arr.resize(n);
    int mw=INT_MAX,jj=-1;
    for(int i=0;i<n;i++){
        cin >> arr[i].S.F >> arr[i].F >> arr[i].S.S;
    }
    sort(all(arr),cmp);
    /*for(int i=0;i<n;i++){
        if(arr[i].S.F < mw){
            mw = arr[i].S.F;
            jj=i;
        }
    }*/


    //dp[arr[0].S.F] = arr[0].S.S;
    //for(int i : dp)
     //   cout << i <<" ";
    //cout << endl;
    for(int i=0;i<n;i++){
        //if(i==jj)
         //   continue;
        int w = arr[i].S.F,s=arr[i].F,v=arr[i].S.S;
        //vi ndp(dp);
        //for(int i=0;i<N;i++)
        //    ndp[i]=dp[i];

        for(int j=min(s,N-w);j>=0;j--){
                dp[w+j] = max(dp[w+j],dp[j]+v);
        }
        //ndp[w] = max(ndp[w],v);
       // deb(i)
       // debarr(ndp)
        //dp = ndp;
    }

    int ans = 0;
    for(int i : dp)
        ans = max(ans,i);//,cout << i <<" ";
        //cout << endl;
    cout << ans <<endl;
}

signed main(){
IOS;
///freopen("input.txt", "r", stdin);
///freopen("output.txt", "w", stdout);
int t=1;
///cin>>t;

for(int tt=0;tt<t;tt++){
   ///cout << "Case #" << tt+1 <<": ";
   mymain();
   }
return 0;
}
/*

*/


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

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n,0);
    rep(i, k){
        int d;
        cin >> d;
        rep(j,d){
            int b;
            cin >> b;
            a[b-1] += 1;
        }
    }
    int ans = 0;
    rep(i,n){
        if(a[i]==0) ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define loop(i,a,b) for(lli i=a;i<b;i++)
#define initialize(array,size,value) for(lli i=0;i<size;i++) array[i]=value
#define couta(array,size) for(lli i=0;i<size;i++) cout<<array[i]<<" "
#define vl vector<lli>
#define vp vector< pair <lli,lli> >
#define sl set<lli>
#define msp multiset < pair < long long , long long > > S;
#define pll pair<lli, lli>
#define mll map<lli, lli>            //for( map<lli, lli>::iterator i=temp.begin();i!=temp.end();i++)cout<<i->fi<<" "<<i->se<<endl;
#define mvl map<lli, vl>
#define umll unordered_map<lli, lli>
#define vt vector<pair<lli, pll >  >
#define vf vector<pair<pll,pll > >
#define qu queue<lli>
#define pq priority_queue<lli>
#define dq deque <lli>
#define ptr vector<lli>::iterator
#define bs(array,x) binary_search(array.begin(),array.end(),x) // also valid for set and multiset
#define lb(array,x) lower_bound(array.begin(),array.end(),x)
#define ub(array,x) upper_bound(array.begin(),array.end(),x)
#define nobw(array,i,j) upper_bound(array.begin(), array.end(), j)-lower_bound(array.begin(), array.end(), i) //number of numbers between i & j
#define vc clear()
#define endl '\n'
#define sp system("pause");
#define INF 9223372036854775807
#define MINF -9223372036854775808
typedef tree<pll,null_type,less<pll>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
//string binary = bitset<32>(n).to_string();
int main()
{
 	ios::sync_with_stdio(0);
    cin.tie(0);
   
	lli a,b;
	cin>>a>>b;
	if(a>=13){
		cout<<b;
	}
	else if(a>=6){
		cout<<b/2;
	}
	else cout<<0;




    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    string s;
    cin>>s;
    bool flag=true;
    for(int i=s.length()-1;i>0;i--){
        if(s[i]=='r'){
            if(i>=6&&s.substr(i-6,7)=="dreamer"){
                i-=6;
                if(i<0)flag=false;
            }
            else if(i>=5&&s.substr(i-5,6)=="eraser"){
                i-=5;
                if(i<0)flag=false;
            }
            else{
                flag=false;
                break;
            }
        }
        else if(s[i]=='m'){
            if(i>=4&&s.substr(i-4,5)=="dream"){
                i-=4;
                if(i<0)flag=false;
            }
            else{
                flag=false;
                break;
            }
        }
        else if(s[i]=='e'){
            if(i>=4&&s.substr(i-4,5)=="erase"){
                i-=4;
                if(i<0)flag=false;
                
            }
            else{
                flag=false;
                break;
            }
        }
        else{
            flag=false;
            break;
        }
    }
    if(flag)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define soja(i,a,n) for(ll i=a;i<=n;i++)
#define ulta(i,n,a) for(ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define ve vector<ll>
#define se set<ll>
#define pll vector<pair<ll,ll>>
#define ma map<ll,ll>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const string space=" ";
int main()
{
    fast;
    bool fg=0;
    ll n,m=100,t,f=0,s=0;
    cin>>n;
 while(1)
 {
     if(n<=m)
        break;
     m+=(m/100);
     f++;
 }
 cout<<f<<endl;
    return 0;
}


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

using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
#define inf 1ll<<60
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
#define int llong
#define be(x) x.begin(), x.end()
typedef pair<int, int> P;


signed main(){
	int N;
	double sum = 0;
	double rate = 38e4;

	cin >> N;
	double x;
	string u;
	for(int i = 0; i < N; i++){
		cin >> x >> u;
		if(u == "JPY")
			sum += x;
		else
			sum += x * rate;
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
main () {
	unsigned int i = 1;
	unsigned int j = 1;
	
	for (i = 1; i < 10; i++) {
		for (j = 1; j < 10; j++) {
			printf("%dx%d=%d\n", i, j, i*j);
		}
	}
	return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include<cstring>
using namespace std;
int main()
{
  int a,b;
  string s,t,u;
  cin>>s>>t;
  cin>>a>>b;
  cin>>u;
  if(s[0]==u[0])
    a=a-1;
  else if(t[0]==u[0])
    b=b-1;
cout<<a<<" "<<b;
   return 0;
}


Measured memory_bytes: 3628
// Problem : A - 500 Yen Coins
// Contest : AtCoder Beginner Contest 150
// URL : https://atcoder.jp/contests/abc150/tasks/abc150_a
// Memory Limit : 1024.000000 MB 
// Time Limit : 2000.000000 milisec 
// Powered by CP Editor (https://github.com/coder3101/cp-editor2)

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr);
 
const int N = 3e5+5;
const int MOD = 1e9+7;

int32_t main()
{
    	IOS;
	int k, x;
	cin >> k >> x;
	if(500*k >= x)
		cout <<"Yes";
	else
		cout <<"No";
    	return 0;
}

Measured memory_bytes: 256