akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

class Main {
    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        char b = inp.next().toCharArray()[0];
        if (b == 'A') System.out.println('T');
        if (b == 'T') System.out.println('A');
        if (b == 'C') System.out.println('G');
        if (b == 'G') System.out.println('C');
        inp.close();
    }
}


Measured memory_bytes: 21716
#include <stdio.h>

#define MAX 100005
#define NIL -1

typedef struct {int p, l, r;} Node;

Node T[MAX];
int n, D[MAX];

void print(int u) {
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if( T[u].p == NIL ) printf("root, ");
  else if( T[u].l == NIL ) printf("leaf, ");
  else printf("internal node, ");

  printf("[");

  for(i=0, c=T[u].l; c != NIL; i++, c=T[c].r) {
    if(i) printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}

void rec(int u, int p) {
  D[u] = p;
  if(T[u].r != NIL) rec(T[u].r,p);
  if(T[u].l != NIL) rec(T[u].l,p+1);
}

int main(void) {
  int i,j,d,v,c,l,r;
  scanf("%d",&n);
  for(i=0;i<n;i++) T[i].p = T[i].l = T[i].r = NIL;
  for(i=0;i<n;i++) {
    scanf("%d %d",&v,&d);
    for(j=0;j<d;j++) {
      scanf("%d",&c);
      if(j==0) T[v].l=c;
      else T[l].r =c;
      l = c;
      T[c].p = v;
    }
  }
  for(i=0;i<n;i++) {
    if(T[i].p == NIL) r = i;
  }
  
  rec(r,0);
  
  for(i=0;i<n;i++) print(i);
  
  return 0;
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
//const ll INF = 1e18;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

int main()
{
    string s;
    cin >> s;
	int ans = 0;
	for(int i = 0; i < s.size(); i++) ans += s[i]-'0';
    cout << max(ans,s[0]-'1'+((int)s.size()-1)*9) << endl;
    return 0;
}

Measured memory_bytes: 256
/*
 _     _                             
| |__ | |__   __ _  __ _ _   _  __ _ 
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
                   |___/ |___/       
*/
#include<bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define mpi         map<pair<ll int,ll int>,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
using namespace std;

#define N  100005

vector<pii> a[N];
ll int vis[N];

ll int ans[N];

void dfs(ll node)
{
	vis[node]=1;
	for(auto i:a[node])
	if(!vis[i.F])
	{
		if(i.S%2==0) ans[i.F]=ans[node];
		else ans[i.F]=1-ans[node];
		dfs(i.F);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		ll int n,m;
		cin>>n;
		m=n-1;
		while(m--)
		{
			ll int x,y,z;
			cin>>x>>y>>z;
			a[x].pb({y,z});
			a[y].pb({x,z});
		}
		ans[1]=1;
		dfs(1);
		for(ll int i=1;i<=n;i++) cout<<ans[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 10880
#include<stdio.h>

int main(){
    long long A, B, C;

    scanf("%lld %lld %lld", &A, &B, &C);

    if(A%2==0 || B%2==0 || C%2==0){
        printf("0");
    }else{
        if(A<=C && B<=C){
            printf("%lld", A*B);
        }else if(B<=A && C<=A){
            printf("%lld", B*C);
        }else if(C<=B && A<=B){
            printf("%lld", C*A);
        }
    }

    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        if (n.length() == 2) {
            System.out.println(n);
        } else {
                System.out.print(n.substring(2, 3 ));
                System.out.print(n.substring(1, 2 ));
                System.out.print(n.substring(0, 1 ));
                System.out.println("");

        }


    }

}

Measured memory_bytes: 23124
O = list(input())
lo = len(O)
E = list(input())
le = len(E)
w = lo + le

X = ['*']*w
for i in range(le):
  X[2*i] =O[i]
  X[2*i+1] = E[i]
if lo > le:
  X[-1] = O[-1]
  
print(''.join(X))

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

int main()
{
  int N;
  vector<bool> b(81, false);
  cin >> N;

  for (int i = 1; i <= 9; i++)
  {
    for (int j = i; j <= 9; j++)
    {
      b[i * j - 1] = true;
    }
  }

  if (b[N - 1])
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3096
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

typedef pair<int, int> P;

int main() {
	string a;
	P data[10];
	for (int i = 0; i < 3; i++) {
		for (int j = 1; j < 4; j++) {
			data[i*3+j].first = 2-i;
			data[i+1+3*(j-1)].second = i;
		}
	}
	while (cin >> a) {
		if (a[0] == '#') {
			break;
		}
		bool hantei = true;
		P R;
		P L;
		R.first = R.second = L.first = L.second = 1;
		int counter = 0;
		for (int i = 0; i < a.size(); i++) {
			if (i == 0) {
				P p = data[a[i]-'0'];
				R = p;
			}else if (hantei) {
				P p = data[a[i]-'0'];
				if (R.second >= p.second) {
					L = p;
					hantei = false;
				} else {
					R = p;
					counter++;
				}
			} else {
				P p = data[a[i]-'0'];
				if (L.second <= p.second) {
					R = p;
					hantei = true;
				} else {
					L = p;
					counter++;
				}
			}
		}
		hantei = false;
		int counter2 = 0;
		R.first = R.second = L.first = L.second = 1;
		for (int i = 0; i < a.size(); i++) {
			if (i == 0) {
				P p = data[a[i]-'0'];
				L = p;
			} else if (hantei) {
				P p = data[a[i]-'0'];
				if (R.second >= p.second) {
					L = p;
					hantei = false;
				} else {
					R = p;
					counter2++;
				}
			} else {
				P p = data[a[i]-'0'];
				if (L.second <= p.second) {
					R = p;
					hantei = true;
				} else {
					L = p;
					counter2++;
				}
			}
		}
		cout << min(counter, counter2) << endl;
	}
	return 0;
}

Measured memory_bytes: 1312
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define vi vector<ll>
#define vii vector<ii>
#define vs vector<string>
#define si set<ll>
#define endl "\n"
#define pb push_back
#define x first
#define y second
//g++ -std=c++11 -Wall -Wextra -pedantic-errors main.cpp -o main
const int ms = 1e5 + 5, base = 31, mod = 1e5 + 7;
using namespace std;

int n, m, dp[ms];
vector<vi > adj;

int solve(int pos){
	if (dp[pos] != -1) return dp[pos];
	
	int best = 0;
	
	for (auto v : adj[pos])
		best = max(best, solve(v)+1);
	
	return dp[pos] = max(dp[pos], best);
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	
	cin >> n >> m;
	adj.resize(n, vi());
	memset(dp, -1, sizeof(dp));
	
	for (int i = 0; i < m; i++){
		int u, v;
		cin >> u >> v;
		u--; v--;
		adj[u].pb(v);
	}
	
	int best = 0;
	for (int i = 0; i < n; i++){
		best = max(best, solve(i));
		/*
		for (auto v : adj[i])
			cout << v+1 << " \n"[v == adj[i][adj[i].size()-1]];
		*/
	}
	
	cout << best << endl;
	
	return 0;
}

Measured memory_bytes: 8192
use std::io;

fn main() {
    let mut buffer = String::new();
    io::stdin().read_line(&mut buffer).unwrap();
    let input_num_vec: Vec<i64> = buffer
        .trim()
        .split_whitespace()
        .map(|c| c.parse().unwrap())
        .collect();

    let first_num = input_num_vec[0];
    let second_num = input_num_vec[1];
    let third_num = input_num_vec[2];

    println!("{} {} {}", third_num, first_num, second_num);
}


Measured memory_bytes: 4352
#include<time.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h> 
int main()
{
	int A[110][110],B[110][110],n,m,l,i,j,k,h;
	long long int C[110][110];
	//读入A
	scanf("%d %d %d",&n,&m,&l);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%lld",&A[i][j]);
	//读入B
	for(i=1;i<=m;i++)
		for(j=1;j<=l;j++)
			scanf("%lld",&B[i][j]);
	//计算C
	for(i=1;i<=n;i++)
		for(j=1;j<=l;j++)
		{
			C[i][j]=0;
			for(k=1;k<=m;k++)
			{
				h=A[i][k]*B[k][j];
				C[i][j]+=h;
				
			}
		}
	//输出
	for(i=1;i<=n;i++)
		for(j=1;j<=l;j++)
		{
			printf("%lld",C[i][j]);
			if(j!=l)
				printf(" ");
			else
				printf("\n");
		}
	return 0;
}


Measured memory_bytes: 2120
//
//  main.cpp
//  ABC123
//
//  Created by hiroaki on 2019/04/16.
//  Copyright © 2019年 hiroaki. All rights reserved.
//

#include <iostream>
using namespace std;

int main() {
    int a,b,c,d,e,k;
    cin >>a>>b>>c>>d>>e>>k;
    int flag = 0;
    if (abs(a-b)>k) {
        flag = 1;
    }
    if (abs(a-c)>k) {
        flag = 1;
    }
    if (abs(a-d)>k) {
        flag = 1;
    }
    if (abs(a-e)>k) {
        flag = 1;
    }
    if (abs(b-c)>k) {
        flag = 1;
    }
    if (abs(b-d)>k) {
        flag = 1;
    }
    if (abs(b-e)>k) {
        flag = 1;
    }
    if (abs(c-d)>k) {
        flag = 1;
    }
    if (abs(c-e)>k) {
        flag = 1;
    }
    if (abs(d-e)>k) {
        flag = 1;
    }
    if(flag==1){
        cout<<":("<<endl;
    }else{
        cout<<"Yay!"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
    private static void solve() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            int d = scanner.nextInt();
            int e = scanner.nextInt();
            int f = scanner.nextInt();
            double x = 0;
            double y = 0;
            if (c * e - b * f != 0) {
                x = (double) (c * e - b * f) / (a * e - b * d);
            }
            if (c * d - a * f != 0) {
                y = (double) (c * d - a * f) / (b * d - a * e);
            }
            System.out.println(String.format("%.3f %.3f", x, y));
        }
    }

    public static void main(String... args) {
        solve();
    }
}

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

typedef long long int int64;
static const int64 MAX = 2000000001LL;
struct vertex {
	int estart;
	int64 dist,ldist;
	int frome;
} v[4003];
struct edge {
	int enext,to;
	int cap;
	int64 cost;
} e[20003];int en;
void addedge(int a,int b,int cap,int64 cost)
{
	e[en].enext = v[a].estart;e[en].to = b;e[en].cap = cap;e[en].cost = cost;v[a].estart = en++;
	e[en].enext = v[b].estart;e[en].to = a;e[en].cap = 0;e[en].cost = -cost;v[b].estart = en++;
}
int n;
int main()
{
	scanf("%d",&n);
	for(int i = 0;i < 6+n+n;++i) {
		v[i].estart = -1;
	}
	for(int i = 6+n;i < 6+n+n;++i) {
		v[i].dist = -4*MAX;
	}
	for(int i = 2;i < 6;++i) {
		v[i].dist = -2*MAX;
	}
	v[1].dist = -4*MAX;
	// 6+n+n
	for(int i = 0;i < n;++i) {
		int64 x,y;int k;
		scanf("%lld%lld%d",&x,&y,&k);
		addedge(0,6+i,k,0);
		addedge(6+i,2,k,x+y); // inf
		addedge(6+i,3,k,x-y);
		addedge(6+i,4,k,-x+y);
		addedge(6+i,5,k,-x-y);
	}
	for(int i = 0;i < n;++i) {
		int64 x,y;int k;
		scanf("%lld%lld%d",&x,&y,&k);
		addedge(6+n+i,1,k,0);
		addedge(2,6+n+i,k,-x-y);
		addedge(3,6+n+i,k,-x+y);
		addedge(4,6+n+i,k,x-y);
		addedge(5,6+n+i,k,x+y);
	}
	int64 cost = 0;
	int flow = 0;
	for(;;) {
		for(int i = 0;i < 6+n+n;++i) {
			v[i].ldist = v[i].dist;
			v[i].dist = -1;
		}
		v[0].dist = 0;
		using pair = std::pair<int64,int>;
		std::priority_queue<pair,std::vector<pair>,std::greater<pair> > pq;
		pq.push(std::make_pair(v[0].dist-v[0].ldist,0));
		while(!pq.empty()) {
			pair curp = pq.top();pq.pop();
			int cur = curp.second;
			int64 dist = curp.first+v[cur].ldist;
			if(v[cur].dist != dist) continue;
			for(int j = v[cur].estart;j != -1;j = e[j].enext) {
				if(e[j].cap == 0) continue;
				int to = e[j].to;
				if(v[to].dist == -1 || v[to].dist > dist+e[j].cost) {
					v[to].dist = dist+e[j].cost;
					v[to].frome = j;
					pq.push(std::make_pair(v[to].dist-v[to].ldist,to));
					assert(v[to].dist-v[to].ldist>=v[cur].dist-v[cur].ldist);
				}
			}
		}
		if(v[1].dist == -1) break;
		int cnt = 99999;
		for(int j = 1;j != 0;j = e[v[j].frome^1].to) {
			int k = v[j].frome;
			if(e[k].cap < cnt) cnt = e[k].cap;
		}
		for(int j = 1;j != 0;j = e[v[j].frome^1].to) {
			int k = v[j].frome;
			e[k].cap -= cnt;
			e[k^1].cap += cnt;
		}
		cost += v[1].dist * cnt;
		flow += cnt;
	}
	printf("%lld\n", -cost);
}


Measured memory_bytes: 1056
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define tez ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main()
{
    tez;
    int n;
    cin>>n;
    
    string s,t;
    cin>>s>>t;
    vector<char>v;
    for(int i=0;i<n;i++)
    {
        v.push_back(s[i]);
        v.push_back(t[i]);
    }
  for(int j=0;j<2*n;j++)
  cout<<v[j];
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define REL

#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <iomanip>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <string>
#include <set>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <cassert>
#include <complex>
#include <stack> 
#include <random>

using namespace std;

typedef int64_t i64;
typedef long long LL;
typedef long long ll;
typedef long double LD;
typedef complex <LD> cld;
typedef unsigned int uint;
typedef complex <double> cd;
typedef unsigned long long ULL;

#define endl "\n"
#define dendl "\n\n"
#define mp make_pair
#define mt make_tuple
#define size(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

/////////////////////////////////////////////////////////////////////

template <typename T>
T sqr(T a) {
	return a * a;
}

template <typename T>
int sign(T a) {
	if (a == 0)
		return 0;
	return (a > 0 ? 1 : -1);
}

template <typename T>
bool uax(T& a, const T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

template <typename T>
bool uin(T& a, const T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template <typename T1, typename T2>
istream& operator >> (istream& in, pair<T1, T2>& p) {
	in >> p.first >> p.second;
	return in;
}

template <typename T1, typename T2>
ostream& operator << (ostream& out, pair<T1, T2>& p) {
	out << p.first << ' ' << p.second;
	return out;
}

mt19937_64 rnd(0);

const int LOG = 30;
const int N = (int)3e5 + 7;
const int MAXN = (int)3e6 + 7;
const int MOD = (int)998244353;
const int INF = (int)1e9 + 7;
const int CONST = 450;
const LL LINF = (i64)1e17;
const LD PI = 3.1415926535897932384626433832795;
const LD EPS = 1;

/////////////////////////////////////////////////////////////////////

void solve() {
	int n, k, cnt[100] = {};
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int x; cin >> x;
		for (int j = 0; j < x; j++) {
			int val; cin >> val;
			cnt[val - 1]++;
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
		ans += cnt[i] == 0;
	cout << ans;
}

int main() {
	double start = clock();
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	cout << fixed << setprecision(20);
	cerr << fixed << setprecision(20);
#else
	cout << fixed << setprecision(20);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	rnd.seed(time(0));
#endif

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

#ifdef _DEBUG
	cout << endl << "Time is " << (clock() - start) / 1000.0;
#endif
}

Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#define rep(i,n) for(ll i = 0; i < (ll)(n); ++i)
using namespace std;
using ll = long long;
const int mod = 1e9+7;

int main()
{
    int n,m;
    cin >> n >> m ;
    int s[m][n]={0};
    int k[m]={0};
    int p[m]={0};
    rep(i,m) {;
        cin >> k[i];
        rep(j,k[i]) cin >> s[i][j];
    }
    rep(i,m) cin >> p[i];

    int ans = 0;
    for( int bit = 0; bit < (1<<n); bit++ ){
        
        bool ok = true;
        rep(i,m){
            int tmp = 0;
            rep(j,n) {
                if ( bit & (1<<j) ) rep(l,k[i]) if( j+1==s[i][l]) tmp ++;
            }
            if( tmp%2 != p[i] ){
                ok = false; 
            }
        }

        if( ok ) ans ++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var s = Console.ReadLine();
        var set = new HashSet<char>();
        for (int i = 0; i < s.Length; i++)
        {
            if (!set.Add(s[i]))
            {
                Console.WriteLine("no");
                return;
            }
        }
        Console.WriteLine("yes");
    }
}


Measured memory_bytes: 13276
#include <bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
using ll = long long;

int main() {
    int N, Q; cin >> N >> Q;
    atcoder::fenwick_tree<ll> bit(N+1);
    for (int i=1;i<=N;i++) {
        int a; cin >> a;
        bit.add(i, a);
    }
    for (int q=0; q<Q; q++) {
        int d, l, r; 
		cin >> d >> l >> r;
        if (d == 0) {
            bit.add(l+1, r);
        } else {
            cout << bit.sum(l+1, r+1) << "\n";
        }
    }
}

Measured memory_bytes: 8220
from __future__ import print_function
import numpy as np
import sys
import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy,functools
# from itertools import accumulate
# from collections import deque
import random

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

n = int(input())

if n%111==0:
    print(n)
else:
    print((int(n/111)+1)*111)


Measured memory_bytes: 13704
//
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define speed ios::sync_with_stdio(false)
using namespace std;

string gs(char x){
    string s(1,x);
    return s;
}

int main()
{
	speed;
	
	ll d,n;
	cin>>d>>n;
	if(n==100)
	{
		if(d==0)
			cout<<101;
		else if(d==1)
			cout<<10100;
		else
			cout<<1010000;
	}
	else
	{
		if(d==0)
			cout<<n;
		else if(d==1)
			cout<<n*100;
		else
			cout<<n*10000;
	}

	
	return 0;
}

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

using namespace std;
#define ll long long int

int main()
{
 ll n;
 cin>>n;
 
 queue<ll> q;
 for(int i=1;i<=9;i++)
 {
     q.push(i);
     
 }
 
 while(!q.empty())
 {
     
     ll k=q.front();
     q.pop();
     n--;
     if(n==0)
     {
         cout<<k;
         break;
         
     }
     
     
     for(ll i=(k%10)-1;i<=(k%10)+1;i++)
     {
         if(i<0 || i>=10)
         continue;
         q.push(k*10+i);
     }
    
 }
 
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

struct UnionFind {
  vector<int> par, rank;
  UnionFind(int n): par(n), rank(n) {
    rep(i,n) par[i] = i;
  }
  int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) par[x] = y;
    else {
      par[y] = x;
      if (rank[x] == rank[y]) rank[x]++;
    }
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  } 
};

void solve() {
  int n, k, l;
  cin >> n >> k >> l;
  vector<int> p(k), q(k);
  rep(i,k) cin >> p[i] >> q[i];
  vector<int> r(l), s(l);
  rep(i,l) cin >> r[i] >> s[i];
  UnionFind road(n);
  UnionFind rail(n);
  rep(i,k) road.unite(p[i] - 1, q[i] - 1);
  rep(i,l) rail.unite(r[i] - 1, s[i] - 1);
  vector<pii> v(n);
  map<pii, int> mp;
  rep(i,n) {
    v[i].first = road.find(i);
    v[i].second = rail.find(i);
    mp[v[i]]++;
  }
  rep(i,n) {
    cout << mp[v[i]] << endl;
  }
}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 20620
#include<map>
#include<queue>
#include<cstdio>
#include<vector>

#define	pb	push_back

using namespace std;

typedef	vector<int>	vi;

vi mv[13];
long long pow12[13];

void findEmptyPos(long long stat,int *z){
	for(int i=0,j=0;i<13;i++){
		if(stat%12==0)	z[j++]=12-i;
		stat/=12;
	}
}

long long sw(long long stat,int i,int j){
	long long powi=pow12[12-i],powj=pow12[12-j];
	int pi=(stat/powi)%12,pj=(stat/powj)%12;
	return stat+(pj-pi)*powi+(pi-pj)*powj;
}

void bfs(map<long long,int> &f,long long inistat){
	f[inistat]=0;
	queue<long long> qu;	qu.push(inistat);
	while(!qu.empty()){
		long long stat=qu.front();	qu.pop();
		int cnt=f[stat];
		if(cnt==10)	break;

		int z[2];	findEmptyPos(stat,z);
		for(int i=0;i<2;i++){
			for(int j=0;j<mv[z[i]].size();j++){
				long long nextstat=sw(stat,z[i],mv[z[i]][j]);
				if(f.count(nextstat)==0){
					qu.push(nextstat);
					f[nextstat]=cnt+1;
				}
			}
		}
	}
}

int main(){
	long long a=1;
	for(int i=0;i<13;i++)	pow12[i]=a,a*=12;

	mv[0].pb(2);
	mv[1].pb(2);	mv[1].pb(5);
	mv[2].pb(0);	mv[2].pb(1);	mv[2].pb(3);	mv[2].pb(6);
	mv[3].pb(2);	mv[3].pb(7);
	mv[4].pb(5);
	mv[5].pb(1);	mv[5].pb(4);	mv[5].pb(6);	mv[5].pb(9);
	mv[6].pb(2);	mv[6].pb(5);	mv[6].pb(7);	mv[6].pb(10);
	mv[7].pb(3);	mv[7].pb(6);	mv[7].pb(8);	mv[7].pb(11);
	mv[8].pb(7);
	mv[9].pb(5);	mv[9].pb(10);
	mv[10].pb(6);	mv[10].pb(9);	mv[10].pb(11);	mv[10].pb(12);
	mv[11].pb(7);	mv[11].pb(10);
	mv[12].pb(10);

	int ans[]={0,1,2,3,4,5,6,7,8,9,10,11,0};
	long long ansstat=0;
	for(int i=0;i<13;i++)	ansstat=ansstat*12+ans[i];

	map<long long,int> f;
	bfs(f,ansstat);

	for(long long inistat;scanf("%lld",&inistat),~inistat;){
		for(int i=1,p;i<13;i++)	scanf("%d",&p),inistat=inistat*12+p;
		map<long long,int> g;
		bfs(g,inistat);

		int cmin=21;
		map<long long,int>::iterator it;
		for(it=g.begin();it!=g.end();it++){
			long long stat=it->first;
			int cnt=it->second;
			if(f.count(stat))	cmin=min(cmin,cnt+f[stat]);
		}
		if(cmin<=20)	printf("%d\n",cmin);
		else	puts("NA");
	}

	return 0;
}

Measured memory_bytes: 1920
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func takahashi(m, d int) int {
	ret := 0
	for i := 22; i <= d; i++ {
		if (i%10) >= 2 && m == (i/10)*(i%10) {
			ret++
		}
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	m, d := nextInt(), nextInt()
	ans := 0
	for i := 1; i <= m; i++ {
		ans += takahashi(i, d)
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
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();
		List<Integer> list = new ArrayList<>();
		for(int i=0; i<n; i++){
			list.add(sc.nextInt());
		}
		list = list.stream().distinct().collect(Collectors.toList());
		System.out.println(list.size());
	}
}


Measured memory_bytes: 36292
#include<bits/stdc++.h>
#include<algorithm>
#define fi first
#define se second
#define ll long long
#define fu(i,a,b) for(ll i=a;i<=b;i++)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
using namespace std;
int main()
{
    ll n , a , b;
    cin >> n >> a >> b;
    if((b - a) % 2 == 0)
    {
        cout<<(b-a)/2;
        return 0;
    }
    ll x = a;
    ll y = n - b + 1;
    cout<<min(x , y) + (b - a)/2;
}


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

int main(){
  int N,sum=0,a=1;
  int an=0,bn=0;
  cin>>N;
  for(int i=0;i<N;i++){
    string s;
    cin>>s;
    for(int j=0;j<s.size()-1;j++){
      if(s.at(j)=='A'&&s.at(j+1)=='B'){
        sum++;
      }
    }
    if(s.at(0)=='B'&&s.at(s.size()-1)!='A'){
      bn++;
      a=0;
    }
    if(s.at(s.size()-1)=='A'&&s.at(0)!='B'){
      an++;
      a=0;
    }
    if(s.at(s.size()-1)=='A'&&s.at(0)=='B'){
      an++;
      bn++;
    }
  }
  if(a==0){
    cout<<sum+min(an,bn)<<endl;
  }else{
    if(min(an,bn)==0){
      cout<<sum<<endl;
    }else{
      cout<<sum+min(an,bn)-1<<endl;
    }
  }
    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
using namespace std;

int main(){
    int N;
    vector<tuple<string, int, int>> a;
    cin >> N;
    for (int i = 1; i <= N; i++){
        string S;
        int P;
        cin >> S >> P;
        a.emplace_back(S,-P,i);
    }
    sort(a.begin(),a.end());
    for (int i = 0; i <= N-1; i++)
    {
        cout << get<2>(a[i]) << endl;
    }


    return 0;
}


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

void push(int);
int pop(void);

int top=0;
int a[100];


int main(){
  int x,i=0;
  char s[100];

  while( scanf("%s", s) != EOF ){
    if ( s[0] == '+' ){
      x = pop();
      x = x + pop();
      push(x);

    } else if ( s[0] == '-' ){
      x = pop();
      x = pop() - x;
      push(x);

    } else if ( s[0] == '*' ){
      x = pop();
      x = x * pop();
      push(x);
      
    } else {
      x = atoi(s);
      push(x);
      

    }
  }
  printf("%d\n",a[1]);

  return 0;
}

void push(int x){
  if(top>=100){
    exit(1);
  }
  top++;
  a[top] = x;
}

int pop(){
  if(top<=0){
    exit(2);
  }
  top--;
  return a[top+1];
}



Measured memory_bytes: 2108
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    n = ni()
    a = nl()

    a.sort()
    ans = [a[-1]]

    right = bisect_left(a, max(a)/2)
    left = right - 1

    if abs(max(a)/2 - a[left]) <= abs(max(a)/2 - a[right]):
        ans.append(a[left])
    else:
        ans.append(a[right])

    if ans[0] == ans[1]:
        ans[1] = 0

    print(*ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 15040
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n;
int a[200010];
int res,mn=1e9;
int main()
{
	cin >>n;
	for (int i=0;i<n;i++) cin >>a[i];
	for (int i=0;i<n;i++)
	{
		mn=min(mn,a[i]);
		if (a[i]<=mn) res++;
	}
	cout <<res;
	return 0;
}

Measured memory_bytes: 1024
/*g++ main.cpp -o main.out*/
/*./main.out*/
/*std::ios::sync_with_stdio(false);cin.tie(0);*/

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

#define LL long long
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define ree(n,a) memset(n,a,sizeof(n));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

string a,b;

int main()
{
    cin>>a>>b;
    for(int i=0;i<max(a.size(),b.size());i++)
    {
        if(i<a.size())cout<<a[i];
        if(i<b.size())cout<<b[i];
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)(x).size())
#define mset(a,v) memset(a,v,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
using namespace std;
typedef long long ll;

char r[128][128];
int a,b;

int main(){
	scanf("%d%d",&a,&b);
	fore(i,0,100)fore(j,0,100)r[i][j]=i<50?'#':'.';
	fore(k,0,a-1)r[k/50*2][k%50*2]='.';
	fore(k,0,b-1)r[99-k/50*2][k%50*2]='#';
	puts("100 100");
	fore(i,0,100)puts(r[i]);
	return 0;
}

Measured memory_bytes: 256
n = int(input())
s = []

for i in range(n):
    s.append(input())

l = [s[i][0] for i in range(n)]

m = l.count('M')
a = l.count('A')
r = l.count('R')
c = l.count('C')
h = l.count('H')

print(m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h)

Measured memory_bytes: 10520
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    A, B, T = map(int, readline().split())

    print(T // A * B)

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9176
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>
#include <map>
#include <vector>
using namespace std;

int main(){
	long long n;
	scanf("%lld", &n);
	printf("%lld\n", n*(n-1)/2);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;

int main(){
  int a, b;
  cin >> a >> b;
  cout << max({a+b, a-b, a*b}) << endl;
}

Measured memory_bytes: 3520
import collections


def main():
    n = int(input())
    *v, = map(int, input().split())

    v0 = count(v[::2])
    v1 = count(v[1::2])

    if len(v0) == 1 and len(v1) == 1:
        if v0[0][0] == v1[0][0]:
            print(n // 2)
        else:
            print(0)
        return

    l0 = min(2, len(v0))
    l1 = min(2, len(v1))

    INF = 10 ** 9
    score = [[0] * l1 for _ in range(l0)]
    for i in range(l0):
        for j in range(l1):
            score[i][j] = sum_v(v0, i) + sum_v(v1, j)
            if i >= l0 or j >= l1 or v0[i][0] == v1[j][0]:
                score[i][j] = INF
    print(min([min(s) for s in score]))


def count(v):
    return collections.Counter(v).most_common()


def sum_v(v, ii):
    return sum([vv[1] for i, vv in enumerate(v) if i != ii])


main()


Measured memory_bytes: 20692
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll int
#define mod 1000000007
#define F first
#define S second
#define mk make_pair
int a[1001]={0};
int ar[21][21]={0};
int main()
{	
	string s;
	cin>>s;
	for(int i=0;i<(int)s.size();i+=2)
	{
		cout<<s[i];
	}
}

Measured memory_bytes: 512
//by xiqiao
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[805][805];
int d[805][805];
int n,m,sx,sy,K,flag;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
vector <pair<int,int> > v[1005];
void solve(int ceng,int xian){
	queue <pair<int,int> > q;
	for(int i=0;i<v[ceng-1].size();i++)q.push(v[ceng-1][i]);
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;q.pop();
		if(d[x][y]!=ceng-1){
			v[ceng].push_back(make_pair(x,y));
		}
		if(d[x][y]>=ceng+K-1)continue;
		for(int i=0;i<4;i++){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<1 || ty<1 || tx>n || ty>m)continue;
			if(xian && s[tx][ty]=='#')continue;
			if(d[tx][ty]>d[x][y]+1){
				d[tx][ty]=d[x][y]+1;q.push(make_pair(tx,ty));
			}
		}
	}
	for(int i=0;i<(int)v[ceng].size();i++){
		d[v[ceng][i].first][v[ceng][i].second]=ceng;
		int x=v[ceng][i].first,y=v[ceng][i].second;
		if(x==1 || y==1 || x==n || y==m){
			flag=1;return;
		}
	}
}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);scanf("%d",&K);
	for(int i=1;i<=n;i++){
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;j++){
			if(s[i][j]=='S'){
				sx=i;sy=j;
			}
		}
	}
	memset(d,0x3f,sizeof(d));
	v[0].push_back(make_pair(sx,sy));d[sx][sy]=0;
	solve(1,1);
	if(flag){
		printf("%d\n",1);return 0;
	}
	v[1].push_back(make_pair(sx,sy));d[sx][sy]=1;
	for(int i=2;;i++){
		solve(i,0);
		if(flag){
			printf("%d\n",i);return 0;
		}
	}
	return 0;
}

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

#pragma region Macro
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define SORT(v) sort(v.begin(), v.end())
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define vvi vector<vector<int>>
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#pragma endregion

void solve(){
	#define int ll
	// ここに処理を記述
	// コンパイル時はエイリアス「gpp」--> c++17でコンパイル
	
	int n;
	cin >> n;

	// 約数の数を愚直に求める --> O(N^2) : 実際に割ってみる
	// ---psuedo code---
	//	ans = 0
	//	for i = 1...N:
	//		for j = 1...N:
	//			if i % j == 0 then ans += i
	//	print ans
	// -----------------
	// i,jでfor文を回す時に、文字を入れ替えても問題ない
	// この状態で問題を再解釈すると
	// 「jの倍数でありN以下である数の総和g(N)に対し、Σ(j=1~N) g(j)を求める」
	// これは等差数列の和
	ll ans = 0;
	FOR(i,1,n+1){
		int l = n/i; // 倍数をとれるlimit
		// g(i)を求める
		ans += l*(l+1)*i/2;
	}

	cout << ans << endl;

}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	
	solve();
	return 0;
}

Measured memory_bytes: 3628
n, *h = map( int, open( 0 ).read().split() )

d = [ 0 ] * n
d[ 1 ] = abs( h[ 1 ] - h[ 0 ] )
for i in range( 2, n ):
  d[ i ] += min( d[ i - 1 ] + abs( h[ i ] - h[ i - 1 ] ), 
                 d[ i - 2 ] + abs( h[ i ] - h[ i - 2 ] ) )
print( d[ n - 1 ] )

Measured memory_bytes: 13876
#include <bits/stdc++.h>
#define rep(i,N) for(int i=0; i<N; i+=1)
using namespace std;

int main() {
  int N;
  cin>>N;
  vector<int>A(N);
  rep(i,N) cin>>A[i];
  int C=0;
  int B=0;
  for(int i=0; i<N-1; i+=1) {
    if(A[i+1]<=A[i]) {
      B+=1;
    }
    else {
      B=0;
    }
    C=max(C,B);
  }
  cout<<C<<endl;
}
    
  


Measured memory_bytes: 640
#include <iostream>
#include <cmath>

using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve(int k) {
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
            for (int l = 1; l <= k; l++) {
                ans += gcd(gcd(i, j), l);
            }
        }
    }
    cout << ans << endl;
}

int main() {
    int k;
    cin >> k;
    solve(k);
    return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a/gcd(a, b) * b;
}

map<ll, ll> prime_factor(ll n) {
  map<ll, ll> ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main()
{
    cout << fixed << setprecision(15);
    ll N;
    cin >> N;

    // for(auto p : prime_factor(2)) {
    //     cout << p.first << ":" << p.second << endl;
    //     M[p.first] += p.second;
    // }

    map<ll, ll> M;

    for(ll i=1; i<=N; i++){
        for(auto p : prime_factor(i)) {
            // cout << p.first << ":" << p.second << endl;
            M[p.first] += p.second;
        }
    }
    
    ll ans = 1;
    for(auto iter=M.begin(); iter!=M.end(); iter++){
        ans = ans * (iter->second + 1);
        ans = ans % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3588
N, M = map(int, input().split())
student = [[0] for _ in range(N+1)]
point = [[0] for _ in range(M+1)]
for i in range(1, N+1):
    student[i] = list(map(int, input().split()))
for i in range(1, M+1):
    point[i] = list(map(int, input().split()))

for i in range(1, N+1):
    this_ans = 0
    pre_min_dict = 2000000001 * 2
    for j in range(1, M+1):
        this_dict = abs(student[i][0] - point[j][0]) + abs(student[i][1] - point[j][1])
        if pre_min_dict > this_dict:
            this_ans = j
            pre_min_dict = this_dict
    print(this_ans)


Measured memory_bytes: 68284
s = input()
s = s[::-1]
word_list = ['dream', 'dreamer', 'erase', 'eraser']
reversed_list = []
for w in word_list:
    reversed_list.append(w[::-1])

can_divide = True
i = 0
while i < len(s):
    # print(s[i:])
    temp_can = False
    for w in reversed_list:
        if s[i:i+len(w)] == w:
            temp_can = True
            i += len(w)
    if not temp_can:
        # print(s[i:])
        can_divide = False 
        break

if can_divide:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int n,t;
ll dp[3100][6100]; //dp[i][j]={i品目まで　食べ終わるのがj分まで の幸せの最大値}
vector<pair<ll,ll>> ab;

int main(){cout<<fixed<<setprecision(10);
		   cin>>n>>t;
           ll a,b;
           ab.resize(n+1);
           for(int i=1;i<=n;i++){
             cin>>a>>b;
             ab[i].first=a;
             ab[i].second=b;
           }
           //入力
           sort(all(ab));
           for(int i=1;i<=n;i++){
            for(int j=0;j<=t+3010;j++){
              
                  dp[i][j]=dp[i-1][j];//i品目を食べない

                  if(j-ab[i].first>=0&&j-ab[i].first<t)//i品目を食べられるか
                    dp[i][j]=max(dp[i][j],dp[i-1][j-ab[i].first]+ab[i].second);//食べた
              
            }
             
             
           }
           
           ll ans=0;
           
           rep(i,0,t+3010){
             
             ans=max(ans,dp[n][i]);
             
           }
           
           cout<<ans<<endl;
}



Measured memory_bytes: 146636
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cfloat>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define int long long
#define ll long long
#define P pair<int,int>
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define all(V) V.begin(),V.end()
#ifdef int
constexpr int INF = LLONG_MAX / 10;
#else
constexpr int INF = INT_MAX / 10;
#endif
constexpr double eps = 1e-9;
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
using namespace std;
inline ll gcd(ll a, ll b) {
	while (b) {
		ll c = a;
		a = b; b = c % b;
	}
	return a;
}
inline ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
bool isprime(ll n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
ll mypow(ll a, ll b) {
	if (!b)return 1;
	if (b & 1)return mypow(a, b - 1) * a;
	int memo = mypow(a, b >> 1);
	return memo * memo;
}
int a[] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
signed main() {
	int k;
	cin >> k;
	cout << a[k - 1] << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
int main() {
	int a,b;
	std::cin >> a>>b;
	if (a > b) {
		std::cout << "a > b" << std::endl;
	}
	else if (a < b) {
		std::cout << "a < b" << std::endl;
	}
	else {
		std::cout << "a == b" << std::endl;
	}
	return 0;
}


Measured memory_bytes: 3080
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int h = scanner.nextInt();
        int w = scanner.nextInt();
        int[][] c = new int[10][10];
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++)
                c[i][j] = scanner.nextInt();

        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++)
                for (int k = 0; k < 10; k++)
                    c[j][k] = Math.min(c[j][k], c[j][i] + c[i][k]);

        long ans = 0;
        for (int i = 0; i < h * w; i++) {
            int a = scanner.nextInt();
            if (a != -1) {
                ans += c[a][1];
            }
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 44404
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll ZERO = 0;
const ll INF = 10000000000;
const ll MOD = 1000000007;
const ll MAX = 55;


int main() {
    ll a,b,x;
    cin >> a >> b >> x;
    if (a != 0 || x == 1){
        printf("%lld\n", b/x - (a-1)/x);
    }
    else{
        printf("%lld\n", b/x - (a-1)/x +1);
    }
}


Measured memory_bytes: 256
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    def n2(x):
        return x*(x+1)//2

    s = input()
    s +='.'
    ans = 0
    p = 0
    n = 0
    prev_p= 0
    for i in range(len(s)-1):
        if s[i] == '>':
            n += 1
            if s[i+1] == '<' or s[i+1] == '.':
                ans += n2(n)
                ans -= min(n, prev_p)
                n = 0
        else:
            p += 1
            if s[i+1] == '>':
                ans += n2(p)
                prev_p = p
                p = 0
            elif s[i+1] == '.':
                ans += n2(p)
                p = 0
    print(ans)




if __name__ == '__main__':
    main()

Measured memory_bytes: 9928
N = int(input())
last = [0,0,0]
for i in range(N):
    ti,xi,yi = map(int,input().split())
    a = ti-last[2] - (abs(xi-last[0])+abs(yi-last[1]))
    if a >= 0  and a % 2 == 0:
        flag = True
    else:
        flag = False
        break
    last = [xi,yi,ti]
if flag:
    print('Yes')
else:
    print('No')
    


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template<Int MOD = 1000000007>
struct Mod{
  Int prev=0;
  vector<Int> fact,inv,finv;
  Mod(){}
  Mod(Int n){init(n);}
  
  Int pow(Int x,Int n){
    Int res=1;
    while(n){
      if(n&1) (res*=x)%=MOD;
      (x*=x)%=MOD;
      n>>=1;
    }
    return res;
  }
  
  Int inverse(Int a){
    return pow(a,MOD-2);
  }
  
  void init(Int n){
    if(prev>=n) return;
    prev=n;
    fact=inv=finv=vector<Int>(n);
    
    fact[0]=1;
    for(Int i=1;i<n;i++)
      fact[i]=(fact[i-1]*i)%MOD;
    
    inv[1]=1;
    for(Int i=2;i<n;i++)
      inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    
    finv[0]=1;
    for(Int i=1;i<n;i++)
      finv[i]=finv[i-1]*inv[i]%MOD;
  }
  
  Int comb(Int n,Int k){
    Int res=1;
    for(Int i=0;i<k;i++){
      res*=(n-i)%MOD;
      res%=MOD;
      res*=inverse(i+1);
      res%=MOD;
    }
    return res;
  }
  
  //only for prime MOD
  Int C(Int n,Int k){
    if(k<0||k>n) return 0;
    return fact[n]*finv[k]%MOD*finv[n-k]%MOD;
  }

  Int H(Int n,Int k){
    return C(n+k-1,n);
  }
  
  Int montmort(Int n){
    Int res=0,rinv=1;
    for(Int k=2;k<=n;k++){
      (rinv*=inverse(k))%=MOD;
      if(k%2) (res+=MOD-rinv)%=MOD;
      else (res+=rinv)%=MOD;
    }
    for(Int i=1;i<=n;i++)
      (res*=i)%=MOD;
    return res;
  }
  
  // calculate P(t) from given points in [0,N]
  Int LagrangePolynomial(vector<Int> &y,Int t){
    Int n=y.size()-1;
    init(n+1);
    Int num=1;
    for(Int i=0;i<=n;i++)
      num=num*((t-i)%MOD)%MOD;
    Int res=0;
    for(Int i=0;i<=n;i++){
      Int tmp=(y[i]*num%MOD)*inverse((t-i)%MOD)%MOD;
      tmp=tmp*finv[i]%MOD;
      tmp=tmp*finv[n-i]%MOD;
      if((n-i)&1) tmp=MOD-tmp;
      res=(res+tmp)%MOD;
    }
    return res;
  }
};

//INSERT ABOVE HERE
signed main(){
  const Int MOD = 1e9+7;
  Mod<MOD> mod(2e5);
  Int n,k;
  cin>>n>>k;
  cout<<mod.H(n,k)<<endl;
  return 0;
}



Measured memory_bytes: 7468
#include<iostream>
#include<stack>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<iomanip>
#include<set>
#include<bitset>
#include<cmath>
#include<numeric>
#include<limits>

#define REP(i, m, n) for(int i = (m); i < (n); i++)
#define rep(i,n) REP(i,0,n)
#define NIL -1
using namespace std;
typedef long long ll;
typedef long long int lli;
static const int MOD = 10000007;
static const int MAX = 100005;


int N;
string s;


int gcd(int a, int b) {
  if ( b > a ) swap(a, b);
  int r = 1;
  while (r > 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

int main(){
  cin >> s;
  N = s.size();
  int cnt = 1;
  rep(i,N) {
    if (i%2 == 0) {
      if (!(s[i] == 'R' || s[i] == 'U' || s[i] == 'D')) cnt = 0;
    } else {
      if (!(s[i] == 'L' || s[i] == 'U' || s[i] == 'D')) cnt = 0;
    }
  }
  if (cnt) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
}


Measured memory_bytes: 256
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

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

void solve() {
	string s;
	cin >> s;
	
	int sz = s.size();
	s += '.';
	vector<int> arr(sz + 1, -1);
	
	if (s[0] == '<') arr[0] = 0;
	if (s[sz - 1] == '>') arr[sz] = 0;
	
	for (int i = 1; i < sz; ++i) {
		if (s[i] == '<' and s[i - 1] == '>') {
			arr[i] = 0;
		}
	}
	
	for (int i = 0; i <= sz; ++i) {
		if (arr[i] == 0) {
			for (int j = i; j < sz and s[j] == s[i]; ++j) {
				arr[j + 1] = max(arr[j] + 1, arr[j + 1]);
			}
			for (int j = i-1; j >= 0 and s[j] == s[i-1]; --j) {
				arr[j] = max(arr[j + 1] + 1, arr[j]);
			}
		}
	}
	
	if (s[sz - 1] == '<') arr[sz] == arr[sz - 1] + 1;
	
	// for (auto x : arr) cout << x << " ";
	cout << accumulate(arr.begin(), arr.end(), 0LL) << "\n";
}

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

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

long long N;
long long abc[100000][3];
long long dp[100000][3];

int main(){
	scanf("%lld",&N);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&abc[i][0]);
		scanf("%lld",&abc[i][1]);
		scanf("%lld",&abc[i][2]);
	}
	dp[0][0] = abc[0][0];
	dp[0][1] = abc[0][1];
	dp[0][2] = abc[0][2];
	for(int i = 1 ; i <= N-1 ; i++){
		for(int j = 0 ; j <= 2 ; j++){
			if (j == 0) dp[i][j] = max(dp[i-1][1]+abc[i][j],dp[i-1][2]+abc[i][j]);
			if (j == 1) dp[i][j] = max(dp[i-1][0]+abc[i][j],dp[i-1][2]+abc[i][j]);
			if (j == 2) dp[i][j] = max(dp[i-1][0]+abc[i][j],dp[i-1][1]+abc[i][j]);
		}
	}
	printf("%lld\n", max(max(dp[N-1][0],dp[N-1][1]),dp[N-1][2]));
	return 0;
}


Measured memory_bytes: 4992