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

// ABC 27-C
// http://abc027.contest.atcoder.jp/tasks/abc027_c
 
public class Main {
	
	static int n;
	static int w;
	static int[] weights;
	static int[] values;
	static HashMap<String, Long> memo;
	
	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in);
		
		n = in.nextInt();
		w = in.nextInt();
		weights = new int[n];
		values = new int[n];
		
		for (int i = 0; i < n; i++) {
			weights[i] = in.nextInt();
			values[i] = in.nextInt();
		}
		memo = new HashMap<String, Long>();
		
		System.out.println(solve2(0, 0));
	}
	
	public static long solve2(int index, long weight) {
		String s = index + "," + weight;
		if (w < weight) {
			return Integer.MIN_VALUE;
		} else if (index == n) {
			return 0;
		} else if (memo.containsKey(s)) {
			return memo.get(s);
		}
		
		long temp = solve2(index + 1, weight);
		if (weight + weights[index] <= w) {
			temp = Math.max(temp, values[index] + solve2(index + 1, weight + weights[index]));
		}
		
		memo.put(s, temp);
		return temp;
	}
	
	public static long solve(int index, long weight, long value) {
		String s = index + "," + weight;
		if (w < weight) {
			return Integer.MIN_VALUE;
		} else if (index == n) {
			return value;
		} else if (memo.containsKey(s)) {
			return memo.get(s);
		}
		
		long temp = Math.max(
				solve(index + 1, weight, value),
				solve(index + 1, weight + weights[index], value + values[index])
		);
		memo.put(s, temp);
		
		return temp;
	}
}

Measured memory_bytes: 61028
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    a,b,c,d=map(int,input().split())
    print('Yes' if abs(a-c)<=d or (abs(a-b)<=d and abs(b-c)<=d) else 'No')
    
resolve()

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

using namespace std;
typedef long long ll;
int n;
int m;
int D[200005];
int T[200005];
map<int, int> cnt;
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> D[i];
        cnt[D[i]] ++;
    }
    cin >> m;
    for(int i = 0; i < m; i ++){
        cin >> T[i];
    }
    for(int i = 0; i < m; i ++){
        if(cnt[T[i]] > 0){
            cnt[T[i]] --;
        }
        else{
            return 0 * printf("NO\n");
        }
    }
    printf("YES\n");
    return 0;
}


Measured memory_bytes: 11264
from collections import defaultdict
d=defaultdict(int)
n=int(input())
a=list(map(int,input().split()))
ans=1
mod=10**9+7
d[-1]=3
for i in a:
  ans*=d[i-1]
  ans%=mod
  d[i-1]-=1
  d[i]+=1
print(ans)

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

int main(){
	string s;
	cin>>s;
	bool f = false;
	if(s[0] == 'A') f = true;
	for(int i=1;i<s.size();i++){
		if(s[i] == 'C' && f){
			cout<<"Yes"<<endl;
			return 0;
		}
		else if(s[i] == 'A'){
			f = true;
		}
		else{
			f = false;
		}
	}
	cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fore(x,a,b) for(int x=a, qwerty=b; x<qwerty; x++)
#define ALL(a) (a).begin(),(a).end()
#define SZ(a) ((int)(a).size())
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define fst first
#define snd second
using namespace std;
typedef long long ll;

const int N=1e5+5;
int n, A[N];

int main(){
        cin >> n;
        fore(x,1,n+1)cin>>A[x];
        A[n+1]=0;
        ll total=0;
        fore(x,0,n+1)total+=abs(A[x]-A[x+1]);
        
        fore(x,1,n+1){
            cout << total - abs(A[x-1]-A[x]) - abs(A[x+1]-A[x]) + abs(A[x-1]-A[x+1]) << "\n";
        }
}


Measured memory_bytes: 1664
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();

        int a[] = new int[number];

        for (int i = 0; i < number; i++) {
            a[i] = scanner.nextInt();
        }
        //最小値
        int intMin = a[0];
        for(int i = 1; i < a.length; i++) {
        	if(intMin > a[i]) {
        		intMin = a[i];
        	}
        }
        
        //最大値
        int intMax = a[0];
        for(int i = 1; i < a.length; i++) {
        	if(intMax < a[i]) {
        		intMax = a[i];
        	}
        }

        /* 総和の計算 */
        long sum = 0;

        for (int i = 0; i < number; i++) {
            sum += a[i];
        }

        System.out.println(intMin + " " + intMax + " " + sum);

	}
}



Measured memory_bytes: 42088
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        int m, h;
        String deck, temp1, temp2;
        Scanner sc = new Scanner(System.in);
        deck = sc.next();
        
        while (!deck.equals("-")) {
            m = sc.nextInt();
            for (int i = 0; i < m; i++) {
                h = sc.nextInt();
                temp1 = deck.substring(0, h);
                temp2 = deck.substring(h, deck.length());
                temp2 += temp1;
                deck = temp2;
            }
            System.out.println(deck);
            deck = sc.next();
        }
    }
}


Measured memory_bytes: 26180
n = int(input())
w_list = list(map(int, input().split()))
ans = 9999999999
for i in range(len(w_list)):
    if ans > abs(sum(w_list[:i]) - sum(w_list[i:])):
        ans = abs(sum(w_list[:i]) - sum(w_list[i:]))
print(ans)


Measured memory_bytes: 2940
li = [str(input()) for i in range(5)]
tmp = []
tmp_2 = []
s = 0
for i in range(5):
    if 10-int(li[i][-1]) != 10:
        tmp.append(10-int(li[i][-1]))
    tmp_2.append(int(li[i]))
tmp.sort()
if len(tmp) != 0:
    print(sum(tmp_2)+(sum(tmp)-tmp[-1]))
else:
    print(sum(tmp_2))

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

#define ll long long //data types used often, but you don't want to type them time by time
#define ull unsigned long long
#define ui unsigned int
#define mod 998244353
#define inf 100000000000010
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0); //to synchronize the input of cin and scanf
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
#define all(x) (x).begin(), (x).end()

typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pi;

bool isprime(ll n)
{
    if(n<=1)return false;
    if(n<=3)return true;
    if(n%2==0||n%3==0)return false;
    for(ll i=5;i*i<=n;i+=6)
    {
        if(n%i==0||n%(i+2)==0)return false;
    }
    return true;
}

ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
        if(b&1)r=(r*a)%m;
        b = b>>1;
        a=(a*a)%m;
    }
    return r%m;
}

struct CustomCompare
{
    bool operator()(const int& lhs, const int& rhs)
    {
        return lhs < rhs;
    }
};

bool comp(pair<ll, ll>a,pair<ll,ll>b)
{
    return a.fi>=b.fi;
}

ll builtin_popcount(ll x)
{
    ll cnt = 0;
    for(ll i=60;i>=0;i--)
    {
        if((1LL<<i)&x)cnt++;
    }
    return cnt;
}

ll addmod(ll a,ll b)
{
    a%=mod;
    b%=mod;
    return (a+b)%mod;
}
ll mulmod(ll a,ll b)
{
    a%=mod;
    b%=mod;
    return (a*b)%mod;
}

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

ll n,k ;cin>>n>>k;
vi arr(n);
rep(i,0,n)cin>>arr[i];
sort(all(arr));
ll sum = 0;
rep(i,0,k)sum+=arr[i];
cout<<sum<<endl;
return 0;
}
/*
50 25
39 99 70 24 49 13 86 43 88 74 45 92 72 71 90 32 19 76 84 46 63 15 87 1 39 58 17 65 99 43 83 29 64 67 100 14 17 100 81 26 45 40 95 94 86 2 89 57 52 91 45
1221 360 459 651 958 584 345 181 536 116 1310 403 669 1044 1281 711 222 280 1255 257 811 409 698 74 838
*/


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

int main(int argc, char const *argv[])
{
	string in;
	string ans[3]={"Sunny","Cloudy","Rainy"};
	while(cin>>in){
		for (int i = 0; i < 3; ++i)
		{
			if (ans[i]==in)
			{
				cout<<ans[(i+1)%3]<<'\n';
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    map<int, int> counts;
    for (int i = 0; i < M; ++i)
    {
        counts[i] = 0;
    }
    for (int i = 0; i < N; ++i)
    {
        int Ki;
        cin >> Ki;
        for (int j = 0; j < Ki; ++j)
        {
            int Aij;
            cin >> Aij;
            ++counts[Aij];
        }
    }
    int count = 0;
    for (const auto &kvp : counts)
    {
        if (kvp.second == N) ++count;
    }
    cout << count << endl;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
def gcd(a, b):
    P = max(a, b)
    Q = min(a, b)
    R = P%Q
    P = Q
    Q = R
    while R != 0:
        R = P%Q
        P = Q
        Q = R
    return P

candidate = [(gcd(A[0], A[1]), True), (A[0], False), (A[1], False)]
for i in range(2, N):
    nxt_cand = []
    for v, b in candidate:
        if(v == 1):
            continue
        if(b == True and gcd(v, A[i]) < v):
            nxt_cand.append((v, False))
            nxt_cand.append((gcd(v, A[i]), True))
        else:
            nxt_cand.append((gcd(v, A[i]), b))
    if(len(nxt_cand)==0):
        nxt_cand = [(1, False)]
    candidate = nxt_cand[::]

print(max(candidate)[0])

Measured memory_bytes: 14400
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int str1 = sc.nextInt();
		int str2 = sc.nextInt();
		if(str1 == 1) str1 = 20;
		if(str2 == 1) str2 = 20;
		if(str1 > str2) System.out.println("Alice");
		if(str1 < str2) System.out.println("Bob");
		if(str1 == str2) System.out.println("Draw");
	}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
void init_fact(){
	kaijo[0]=1;
	for(int i=1;i<=2000000;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	if(!kaijo[0])init_fact();
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int inv(int x){
	x=modpow(x,MOD-2);
	return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
double dist(double ax,double ay,double bx,double by){
	return sqrt((bx-ax)*(bx-ax)+(ay-by)*(ay-by));
}

signed main(){
	int n;
	string s;
	cin>>n>>s;
	rep(i,s.size())cout<<(char)('A'+(((s[i]-'A')+n)%26));
	cout<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF ((long long)1e13)
using namespace std;
int n,W;
long long w,v;
long long bst[100005];
int main() {
	scanf("%d%d",&n,&W);
	for(int i=1; i<=1e5+1; i++) bst[i]=INF;
	for(int i=0; i<n; i++) {
		scanf("%lld%lld",&w,&v);
		for(int j=1e5; j>=v; j--) {
			bst[j]=min(bst[j],bst[j-v]+w);
		}
	}
	int ans=0;
	for(int i=1; i<=1e5+1; i++) {
		if(bst[i]<=W) {
			ans=i;
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (int i=0;i<N;i++)
#define loop(i,N,M) for(int i=N;i<M;i++)

//変数
ll N, M;
vector<ll> p,x,y;

class UnionFind
{
public:
	UnionFind(ll size) : parent(size), rank(size) {
		for (ll i = 0; i < size; i++) {
			parent[i] = i;
			rank[i] = 0;
		}
	};

	ll root(ll x) {
		if (parent[x] == x) {
			return x;
		}
		else {
			return parent[x] = root(parent[x]);
		}
	}

	bool same(ll x, ll y) {
		return root(x) == root(y);
	}

	void unite(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return;

		if (rank[x] < rank[y]) {
			parent[x] = y;
		}
		else {
			parent[y] = x;
			if (rank[x] == rank[y]) rank[x]++;
		}
	}

private:
	//parent[i]==j  : iの親がj
	vector<ll> parent;
	vector<ll> rank;

};

//解法
void solve() {

	UnionFind UF(N);

	rep(i, M) {
		UF.unite(x[i] - 1, y[i] - 1);
	}

	ll ans = 0;
	rep(i, N) {
		if (UF.same(p[i]-1, p[p[i]-1]-1) == true) {
			ans++;
		}
	}

	cout << ans;

	return;
}

int main() {
	//入力
	cin >> N >> M;
	p.resize(N);
	x.resize(M);
	y.resize(M);
	rep(i, N) cin >> p[i];
	rep(i, M) cin >> x[i] >> y[i];
	solve();
	cout << endl;
	return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int Nmax=200010;
 
int main() {
	int A,B,C;
	cin >> A >> B >> C;
	if(A+B >= C) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI (acos(-1))
#define ct cout<<
#define cn cin>>
#define spc <<" "<<
#define nl puts("")
#define _fl(x) puts("FLAG " #x),fflush(stdout);
#define  _(x)  cout<< #x <<" is "<< x <<endl;
#define fs first
#define sc second
#define pb push_back
#define all(v)  (v).begin(), (v).end()
#define _109 (1000000000)
#define _0(arr) memset(arr,0,sizeof ( arr ) )
#define _1(arr) memset(arr,-1,sizeof ( arr ) )
#define _ninp(n,arr) for(int i=0; i<n;i++)cin>>arr[i];
#define _nout(n,arr) for(int i=0; i<n;i++)cout<<arr[i]<<" \n"[i==n-1];
double _eps=1e-6;


int main() {

    string s;
    cn s;
    ct s[0]<<s[1]<<s[2];nl;







    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pb push_back
int dp[1100];
int main(){
	memset(dp,0x00,sizeof dp);
	dp[0]=1;
	for (int i=1;i<=1000;i++){
		if (i>=4) dp[i]|=dp[i-4];
		if (i>=7) dp[i]|=dp[i-7];
	}
	int n; scanf("%d",&n);
	if (n>1000||dp[n]) puts("Yes"); else puts("No");
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var A, B int
	fmt.Scan(&A, &B)

	max := A + B
	if max < A-B {
		max = A - B
	}
	if max < A*B {
		max = A * B
	}

	fmt.Println(max)
}


Measured memory_bytes: 512
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define dump(a) (cerr << #a << " = " << (a) << endl)
#define REP(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) REP(i, 0, n)
#define ALL(x) begin(x), end(x)

constexpr int LEN = 8;

int main() {
  for(int n, m; cin >> n >> m && (n | m);) {
	vector<tuple<bool, vector<int>, string>> rules;
	
	set<string> permit, deny;

	rep(i, n) {
	  string which, source, destination;
	  cin >> which >> source >> destination;

	  const string sum = source + destination;
	  vector<int> pos;
	  rep(j, sum.size()) {
		if(sum[j] == '?') pos.emplace_back(j);
	  }

	  const bool is_permit = (which[0] == 'p');
	  auto &S = (is_permit ? permit : deny);

	  rules.emplace_back(is_permit, pos, sum);
	  S.insert(sum);
	}

	reverse(ALL(rules));
	vector<tuple<string, string, string>> match;

	rep(i, m) {
	  string source, destination, body;
	  cin >> source >> destination >> body;

	  for(const auto &rule : rules) {
		string sum = source + destination;

		for(const auto &pos : get<1>(rule)) {
		  sum[pos] = '?';
		}

		if(get<2>(rule) == sum) {
		  if(get<0>(rule)) match.emplace_back(source, destination, body);
		  break;
		}
	  }
	}

	cout << match.size() << endl;
	for(const auto &e : match) {
	  cout << get<0>(e) << " " << get<1>(e) << " " << get<2>(e) << endl;
	}
  }

  return 0;
}

Measured memory_bytes: 1452
N,K = map(int,input().split())
h = [int(input()) for _ in range(N)]

h.sort()
min = h[K-1] - h[0]
for i in range(1 , N - K + 1):
    if min > h[i + K - 1] - h[i]:
        min = h[i + K - 1] - h[i]

print(min)

Measured memory_bytes: 7484
S=input()
Q=int(input())
inv = 0
s0 = ""
s1 = ""
for i in range(Q):
  q = input()
  if q[0] == "1":
    if inv == 0: inv = 1
    else: inv = 0
  else:
    q,f,c = q.split()
    if f == "1":
      if inv == 0:
        s0 += c
      else:
        s1 += c
    else:
      if inv == 1:
        s0 += c
      else:
        s1 += c
if inv == 1:
  S = s1[::-1] + S[::-1] + s0
else:
  S = s0[::-1] + S + s1

print(S)


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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v.at(i);
    }

    bool lightTwo = false;
    int lightIdx = 1;
    int cnt = 0;
    while (lightTwo == false && cnt < v.size()) {
        lightIdx = v.at(lightIdx - 1);
        cnt++;
        if (lightIdx == 2) {
            lightTwo = true;
            break;
        }
    }

    if (lightTwo) {
        cout << cnt << endl;
    } else {
        cout << -1 << endl;
    }
}


Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int N = 29;

char a[N][N];
int d[N][N];
int qr[N * N];
int qc[N * N];

int main() {
  int h, w;
  scanf("%d%d", &h, &w);
  for (int i = 0; i < h; ++i) {
    scanf("%s", a[i]);
  }
  int ans = 0;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (a[i][j] == '#') {
        continue;
      }
      for (int ii = 0; ii < h; ++ii) {
        for (int jj = 0; jj < w; ++jj) {
          d[ii][jj] = -1;
        }
      }
      d[i][j] = 0;
      qr[0] = i;
      qc[0] = j;
      for (int qh = 0, qt = 1; qh < qt; ++qh) {
        int r = qr[qh];
        int c = qc[qh];
        for (int dr = -1; dr <= 1; ++dr) {
          for (int dc = -1; dc <= 1; ++dc) {
            if (abs(dr) + abs(dc) != 1) {
              continue;
            }
            int nr = r + dr;
            int nc = c + dc;
            if (nr < 0 || nr >= h || nc < 0 || nc >= w || a[nr][nc] == '#') {
              continue;
            }
            if (d[nr][nc] == -1) {
              d[nr][nc] = d[r][c] + 1;
              qr[qt] = nr;
              qc[qt] = nc;
              ++qt;
            }
          }
        }
      }
      for (int ii = 0; ii < h; ++ii) {
        for (int jj = 0; jj < w; ++jj) {
          ans = max(ans, d[ii][jj]);
        }
      }
    }
  }
  printf("%d\n", ans);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
const int N=3e5+5;
const int MOD=1e9+7;
int a[N];

int cmp(int a,int b)
{
    return a>b;
}
string s;
map<ll,int> mp;
const int minn=-1e9-10;
int b[N];
const int maxx=1e9+10;
int main()
{
    cin>>s;
    ll ans=0;
    for(int i=0;i<s.size();i++){
        ans+=s[i]-'0';
        ans%=9;
    }
    if(ans==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}






Measured memory_bytes: 3752
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int MAXN = 200005;

int n, ans, a[MAXN], f[MAXN], pos[MAXN];

int main(){
	scanf( "%d", &n );
	for( int i = 1; i <= n; ++i ){
		scanf( "%d", &a[i] );
		pos[a[i]] = i;
	}
	for( int i = 1; i <= n; ++i ){
		ans = max( ans, ++f[i] );
		f[ pos[a[i]+1] ] = max( f[ pos[a[i]+1] ], f[i] );
	}
	printf( "%d\n", n - ans );
	return 0;
}

Measured memory_bytes: 2560
//#define MYDEBUG
#include <bits/stdc++.h>
#ifdef MYDEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#define ifcin(x) std::ifstream cin(x)
#else
#define debug(x)
#define ifcin(x)
#endif
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define all(x) x.begin(), x.end()
#define rep(i,from,to) for(int i=from; i<to; ++i)
#define REP(i,from,to) for(int i=from; i<=to; ++i)
using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::ostream;
using std::swap;
using std::max;
using std::min;
using std::queue;
typedef struct edge edge;
typedef struct unionfind unionfind;
typedef struct Graph Graph;

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  size_t last = v.size() - 1;
  for (size_t i = 0; i < v.size(); ++i) {
    out << v[i];
    if (i != last)
      out << ",";
  }
  out << "]";
  return out;
}

struct unionfind{
	vector<int> par;
	vector<int> rank;
	unionfind(int n) {
		par = vector<int>(n);
		rank = vector<int>(n);
		rep(i,0,n){//0????????????
			par[i] = i;
			rank[i] = 1;
		}
	}
	
	int find(int x){
		if(par[x] == x){
			return x;
		}
		return par[x] = find(par[x]);
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
	
	void unite(int x, int y){//rank[x] > rank[y]?????????
		x = find(x);
		y = find(y);
		if(x == y){
			return;
		}
		if(rank[x] < rank[y]){
			swap(x,y);
		}
		par[y] = x;
		rank[x] += rank[y];
		rank[y] = 0;
	}
	
	int size(int x){
		return rank[x];
	}
};

struct edge{
	int from, to, cost;
	edge(int from, int to, int cost){
		this->from = from;
		this->to = to;
		this->cost = cost;
	}
	
	edge(){
		*this = edge(-1,-1,-1);
	}
	
	bool operator<(const edge& e) const{
		return cost < e.cost;
	}
};

class Graph{
	public:
	static int kruskal(vector<edge>& es, int n){
		sort(all(es));
		int min_cost = 0;
		unionfind uf(n);
		rep(i,0,es.size()){
			edge& e = es[i];
			if(!uf.same(e.from, e.to)){
				min_cost += e.cost;
				uf.unite(e.from, e.to);
			}
		}
		return min_cost;
	}
};


int V,E;
vector<edge> es;
void solve(){
	ifcin("/storage/emulated/0/AppProjects/past15/jni/in.txt");
	cin >> V >> E;
	rep(i,0,E){
		int s,t,d;
		cin >> s >> t >> d;
		es.push_back(edge(s,t,d));
	}
	cout << Graph::kruskal(es, V) << endl;
}

int main() {
	solve();
}

Measured memory_bytes: 4452
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int main()
{
	int n, k, q;
	cin >> n >> k >> q;
	int cnt[100001] = {};
	for(int i = 0; i < q; i++){
		int a;
		cin >> a;
		a--;
		cnt[a]++;
	}
	for(int i = 0; i < n; i++){
		if(k - (q - cnt[i]) > 0) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

Measured memory_bytes: 1024
#include<stdio.h>
//#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<set>
#include<queue>
#include<stdlib.h>
#include<string.h>
#include<vector>
using namespace std;
#define inf 1e9+7
int min(int a,int b) {return a<b?a:b;}
#define mem(a,b) memset(a,b,sizeof(a))
int main()
{
     int a[3];
     scanf("%d%d%d",&a[0],&a[1],&a[2]);
     sort(a,a+3);
     printf("%d\n",a[0]*a[1]/2);
}


Measured memory_bytes: 128
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>

using namespace std;

int main(){

    int n,k;
    cin >> n >> k;

    long long int a[n];
    for(int i=0;i<n;i++)cin >> a[i];

    long long int S=1000000000000000;

    for(int b=0;b<(1<<n);b++){
        if(__builtin_popcount(b)!=k) continue;

        long long int c[n];
        for(int i=0;i<n;i++)c[i]=a[i];

        long long int s=0;

        for(int i=1;i<n;i++){
            if(b&(1<<i)){
                long long int p=0;
                if(*max_element(c,c+i)>=c[i]){
                    p=*max_element(c,c+i)+1-c[i];
                    c[i]=*max_element(c,c+i)+1;
                }
                s+=p;
            }
        }

        S=min(s,S);

    }

    cout << S << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);

using namespace std;

ll power(ll x,ll y) 
{ 
	if(x == 0) 
        return 0; 
    if (y == 0) 
        return 1; 
    else if (y % 2 == 0) 
        return power(x, y / 2) * power(x, y / 2); 
    else
        return x * power(x, y / 2) * power(x, y / 2); 
} 

int main()
{
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif

    fastio
    ll t, i, j, x;
    cin>>x;
    if(360%x==0)
    {
    	cout<<360/x;
    }
    else
    {
    	for(i=2; ; i++)
    	{
    		ll num=360*i;
    		if(num%x==0)
    		{
    			cout<<num/x;
    			break;
    		}
    	}
    }
    
}

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

void sakujo(vector<vector<string>> &m,int n){

}

int main(){
    int h,w;
    cin>>h>>w;
    vector<string> m(h);
    for(int i=0;i<h;++i){
        cin>>m[i];
    }
    vector<bool> hi(h,false);
    vector<bool> wi(w,false);
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(m[i][j]=='#'){
                hi[i]=true;
                wi[j]=true;
            }
        }
    }
    for(int i=0;i<h;++i){
        if(hi[i]){
            for(int j=0;j<w;++j){
                if(wi[j]){
                    cout<<m[i][j];
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
N=int(input())
A=sorted(list(map(int,input().split())))

C=[1 for i in range(10**6+1)]
for i in range(N):
    if C[A[i]]==0:  #すでに割り切るものがあるとわかった場合
        continue
    if C[A[i]]==-1:  #同じ数字を2回目に通った時
        C[A[i]]=0
        continue
    C[A[i]]*=-1  #通ったの印
    j=2
    while A[i]*j<=10**6:  #それの倍数はすべてダメ
        C[A[i]*j]=0
        j+=1

print(C.count(-1))

Measured memory_bytes: 33416
#include<iostream>

using namespace std;

int main()
{
	int n;
	int* a;

	cin >> n;
	a = new int[n];

	for (int i = 0; i < n; i++)
		cin >> a[i];

	for (int i = n - 1; i > -1; i--)
	{
		if (i != 0)
			cout << a[i] << " ";
		else
			cout << a[i];
	}

	cout << endl;
}

Measured memory_bytes: 3096
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    long long W, H, x, y;
    cin >> W >> H >> x >> y;
    double res = (double)(W) * H / 2;
    cout << fixed << setprecision(10) << res << " ";

    if (x*2 == W && y * 2 == H) cout << 1 << endl;
    else cout << 0 << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Nmax = 1e5;
const int P = 1e9+7;
int N, X;
int S[Nmax];

int main(){
	cin >> N >> X;
	for(int i=0; i<N; i++) cin >> S[i];

	sort(S, S+N, greater<int>());
	vector<vector<ll> > dp(N+1, vector<ll>(X+1));
	dp[0][X] = 1;
	for(int i=0; i<N; i++){
		for(int j=0; j<=X; j++){
			dp[i][j] %= P;
			dp[i+1][j%S[i]] += dp[i][j];
			dp[i+1][j] += (N-1-i)*dp[i][j]%P;
		}
	}

	ll ans = 0;
	for(int j=0; j<=X; j++){
		ans = (ans+j*dp[N][j])%P;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 158592
#include <iostream>
#include <cmath>
using namespace std;

int main(void){
  long long n,p,q;
  
  cin >> n;
  for (p=sqrt(n)+1; p>0; p--){
    if (n%p==0) break;
  }
  q = n/p;
  cout << (p+q-2) << endl;
  return 0;
}


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

int main() {
	ll h, w, ans = 1;
	ios_base::sync_with_stdio(0), cin.tie(0);
	if (cin >> h >> w, h > 1 and w > 1) {
		if (ans = h*(w>>1), w&1)
			ans += h>>1, ans += h&1; }
	cout << ans; }

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

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    cin >> n >> m;
    for(i=0;i<m;i++){
        cin >> j;
        n-=j;
    }
    if(n>=0){
        cout << n << endl;
    }else{
        cout << -1 << endl;
    }
    return 0;
}

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

using namespace std;
typedef long long ll;
const ll mx = 10000007;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
#define gcd(a, b) __gcd((a), (b))
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
#define FIO ios_base::sync_with_stdio(false);  cin.tie(NULL);


int main() {

    ll n, k;
    cin >> n >> k;
    ll a[n];
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll i = 0, c = 0;
    while(i < n - 1) {
        i += k - 1;
        c++;
    }
    cout << c << endl;
    return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<double,double> dd;
typedef pair<ll,ll> pll;
typedef pair<string,int> psi;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<int> > vvi;
typedef vector<vector<ll> > vvll;
typedef vector<vector<ii> > vvip;
typedef vector<ii> vii;
#define pb push_back
#define F first
#define S second
#define MOD 1000000007
#define NA -1
#define ALL(v) v.begin(),v.end()
#define mp make_pair
#define rep(i, n) for (int (i) = 0; (i) < (n); (i) ++)
#define rep1(i, n) for (int (i) = 1; (i) <= (n); (i) ++)
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define db(x) {cout << #x << " = " << (x) << endl;}
#define dba(a, x, y) {cout<<#a<<" :";FOR(i123,x,y)cout<<setw(4)<<(a)[i123];cout<<endl;}
#define foreach(e, x) for (__typeof(x.begin()) e = x.begin(); e != x.end(); e++)
#define clr(x) memset(x,0,sizeof(x));
#define sz(x) int((x).size())
#define endl '\n'
const int INF = INT_MAX;
const ll INFL = LLONG_MAX;

//const ld PI = acos(-1);
#define PI acos(-1)
#define re return 
typedef pair<pll,ll> ppll;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int main () 
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	ios_base::sync_with_stdio(0); cout.precision(15); cout << fixed; cout.tie(0); cin.tie(0);
	int n;
	cin>>n;
	vi v(2*n);
	rep(i,2*n)
	  cin>>v[i];
	  sort(ALL(v));
	  ll ans=0;
	  for(int i=0;i<sz(v);i+=2)
	  	ans+=min(v[i],v[i+1]);
	  cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <iomanip>
#include <cstdio>

using namespace std;

int main() {
    int W, H, x, y;
    cin >> W >> H >> x >> y;
    printf("%.8lf %d\n", double(W)*double(H)/2, (x + x) == W && (y + y) == H);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll= long long ;
using P = pair<ll,ll>;
#define rep(i,n) for (ll i = 0; i<(ll)(n); i++)
#define mod 1000000007
#define pi 3.141592653589793
typedef vector<ll> vcl;

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a, ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t =rep_jijo(n,x/2);
        return t*t%mod;
  }
  return n*rep_jijo(n,x-1)%mod;
}


int main() {
ll n;
cin>>n;
set<string>gc;
string s;
rep(i,n){
    cin>>s;
    gc.insert(s);
}

cout<<gc.size()<<endl;
return 0;
}



Measured memory_bytes: 19212
#include<iostream>
#include<vector>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;

int main(){
	int n; cin>>n;
	vector<int>a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int ans=1;
	int key=a[0];
	if(key==2){
		cout<<1<<endl;
		return 0;
	}
	while(1){
		key=a[key-1];
		ans++;
		if(key==2)break;
		if(ans>n){
			cout<<-1<<endl;
			return 0;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <stdio.h>

int main () {
  int N, M;
  int A[100];
  
  scanf("%d %d", &N, &M);
  for (int i = 0;i < N; i++)
    scanf("%d", &A[i]);
  
  
  int total = 0;
  for (int i = 0;i < N; i++)
    total = total + A[i];
  
  int count = 0;
  for (int i = 0;i < N; i++)
  {
    if (A[i] >= total / (4.0 * M))
      count = count + 1;
  }
  
  if (count >= M)
    printf("Yes\n");
  else
    printf("No\n");
  
  return 0;
}

Measured memory_bytes: 1664
n,x = map(int,input().split())
a = list(map(int,input().split()))
count= 0
for i in range(n-1):
    count += max(0,a[i]+a[i+1]-x)
    if a[i]+a[i+1] > x :
        if (a[i]+a[i+1]-x) > a[i+1]:
            a[i+1] = 0
        else:
            a[i+1] -= (a[i]+a[i+1]-x)
print(count)

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


int main(){
  int n;
  cin >> n;
  vector<string> s(n);
  for(int i=0;i<n;++i){
    cin >> s[i];
  }
  int ab_num=0;
  int a,b;
  a=0;
  b=0;
  int ba=0;
  for(int i=0;i<n;++i){
    int siz=s[i].size();
    if(s[i][0]=='B' && s[i][siz-1]!='A') b++;
    if(s[i][siz-1]=='A' && s[i][0]!='B') a++;
    if(s[i][0]=='B' && s[i][siz-1]=='A') ba++;
    for(int j=1;j<s[i].size();++j){
      if(s[i][j-1]=='A' && s[i][j]=='B'){
        ab_num++;
      }
    }
  }
  int ans=ab_num;
  if(ba==0){
    ans+=min(b,a);
  }else if(ba!=0 && a+b>0){
    ans+=ba+min(a,b);
  }else if(a+b==0){
    ans+=(ba-1);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 768
# ABC133 E
from collections import deque
N,K=map(int,input().split())
p=10**9+7
G=[[] for _ in [0]*(N+1)]
for _ in [0]*(N-1):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    
D=[-1]*(N+1)
F=set()
color=[K]*(N+1)

res=1
D[1]=0
q=deque()
q.append(1)
while q:
    node=q.pop()
    if node in F:
        continue
    if D[node]>1:
        color[node]-=1
    if color[node]<=0:
        res*=0
    else:
        res=(res*color[node])%p
    F.add(node)
    i=1
    for next_node in G[node]:
        if D[next_node]>=0:
            continue
        D[next_node]=D[node]+1
        color[next_node]-=i
        i+=1
        q.append(next_node)
print(res%p)

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

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> edges[1000];
    for(int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        edges[a-1].push_back(b-1);
    }

    vector<int> ans;
    for(int s=0; s<N; s++){
        bitset<1000> visited;
        vector<int> prv(N);
        queue<int> que;
        que.push(s);
        visited[s] = 1;
        while(que.size()){
            int i = que.front(); que.pop();
            for(int j : edges[i]){
                if(j == s){
                    vector<int> res = {i};
                    while(i != s){
                        i = prv[i];
                        res.push_back(i);
                    }
                    reverse(res.begin(), res.end());
                    if(ans.size() == 0 || ans.size() > res.size()){
                        ans = res;
                    }
                    while(que.size()) que.pop();
                    break;
                }
                if(visited[j]) continue;
                visited[j] = 1;
                prv[j] = i;
                que.push(j);
            }
        }
    }
    if(ans.size()){
        cout << ans.size() << endl;
        for(int a : ans) cout << a+1 << endl;
    }else{
        cout << -1 << endl;
    }
}


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

ll INF = 1e+18;
int iINF = 1e9;
int MAXI = 1e8 + 1;
using vec = vector<int>;

void
rec(int i, vec& arr, vec& dp)
{
  if(i == 0) {
    dp[0] = 0;
    return;
  }
  if(dp[i] != iINF) return ;

  rec(i - 1, arr, dp);
  if(dp[i] > dp[i - 1] + abs(arr[i] - arr[i - 1])) dp[i] = dp[i - 1] + abs(arr[i] - arr[i - 1]);
  if(i > 1){
    if(dp[i] > dp[i - 2] + abs(arr[i] - arr[i - 2])) dp[i] = dp[i - 2] + abs(arr[i] - arr[i - 2]);
  }

  return ;
}

int 
main()
{
  int N; cin >> N;
  vector<int> arr(N);
  rep(i, 0, N) cin >> arr[i];
  vector<int> dp(N, iINF);

  rec(N - 1, arr, dp);
  cout << dp[N - 1] << endl;

}

Measured memory_bytes: 8740
N = gets.to_i

a = Array.new(N + 1, 0)
[*1 ... Math.sqrt(N)].repeated_permutation(3) do |x, y, z|
  v = x**2 + y**2 + z**2 + x*y + y*z + z*x
  a[v] += 1 if v <= N
end
puts a[1 .. N]

Measured memory_bytes: 14248
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

typedef db T;
const db eps = 1e-8;
int sgn(T x){return (x>eps)-(x<-eps);}
struct P{
    T x,y;
    P(){} P(T x,T y):x(x),y(y){}
    void read(){scanf("%lf%lf",&x,&y);}
    P operator - (const P&b) const {return P(x-b.x,y-b.y);}
    P operator + (const P&b) const {return P(x+b.x,y+b.y);}
    T operator * (const P&b) const {return x*b.x+y*b.y;}
    P operator * (const T&k) const {return P(x*k,y*k);}
    T operator ^ (const P&b) const {return x*b.y-y*b.x;}
};
T norm(P a){return a*a;}
P proj(P p,P a,P b){return (b-a)*((p-a)*(b-a)/norm(b-a))+a;}
T abs(P a){return sqrt(norm(a));}
struct L{
    P s,t;
    L(){} L(P s,P t):s(s),t(t){}
    void read(){s.read();t.read();}
};

bool isSS(L a,L b){ // seg x seg , replace x->y to accelerate
    T c1=(a.t-a.s)^(b.s-a.s),c2=(a.t-a.s)^(b.t-a.s);
    T c3=(b.t-b.s)^(a.s-b.s),c4=(b.t-b.s)^(a.t-b.s);
    return sgn(c1) * sgn(c2) <= 0 && sgn(c3) * sgn(c4) <= 0 &&
        sgn(max(a.s.x,a.t.x) - min(b.s.x,b.t.x)) >= 0 &&
        sgn(max(b.s.x,b.t.x) - min(a.s.x,a.t.x)) >= 0 &&
        sgn(max(a.s.y,a.t.y) - min(b.s.y,b.t.y)) >= 0 &&
        sgn(max(b.s.y,b.t.y) - min(a.s.y,a.t.y)) >= 0;
}
bool inRegion(T a,T p,T b) {return sgn(a-p)==0||sgn(b-p)==0||(a<p!=b<p);}
bool inRec(P p,L a){
    return inRegion(a.s.x,p.x,a.t.x) && inRegion(a.s.y,p.y,a.t.y);
}
db disPL(P p,L a){
    P q=proj(p,a.s,a.t);
    if(inRec(q,a)) return abs(p-q);
    return min(abs(p-a.s),abs(p-a.t));
}
db disSS(L a,L b){
    if(isSS(a,b)) return 0;
    return min(min(disPL(a.s,b),disPL(a.t,b)),min(disPL(b.s,a),disPL(b.t,a)));
}

int main(){
    int Q;scanf("%d",&Q);
    rep(i,0,Q){
        L a,b;a.read();b.read();
        printf("%.10f\n",disSS(a,b));
    }
    return 0;
}

Measured memory_bytes: 3232
#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int N, T, A;
    cin >> N >> T >> A;
    int ans = 0;
    double min = 100000;
    for(int i = 0; i < N; i++)
    {
        int H;
        cin >> H;
        double d = abs((T - (H*0.006)) - A);
        if (min > d) {
            min = d;
            ans = i + 1;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n , a[N] , b[N] , c[N] , dp[N][100];
int calc(int i , char selected){
    if(i == n)
        return 0;
    if(dp[i][selected] != -1)
        return dp[i][selected];
    int choseA , choseB , choseC;
    choseA = choseB = choseC = 0;

    if(selected != 'a')
        choseA = a[i] + calc(i + 1, 'a');
    if(selected != 'b')
        choseB = b[i] + calc(i + 1, 'b');
    if(selected != 'c')
        choseC = c[i] + calc(i + 1 , 'c');
    return dp[i][selected] = max(choseA , max(choseB , choseC));
}
int main(){
    cin >> n ;
    for(int i = 0 ; i < n ; i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    memset(dp, -1 , sizeof dp);
    cout << calc(0 , '0');
    return 0;
}

Measured memory_bytes: 51584
#include<iostream>
#include<stdlib.h>
#include<string.h>

using namespace std;

typedef struct BiTNode{
public:
  int key;
  struct BiTNode *parent;
  struct BiTNode *left;
  struct BiTNode *right;

  BiTNode(int key){
    this->key = key;
    this->parent = NULL;
    this->left = NULL;
    this->right = NULL;
  }
} BiTNode;

typedef struct BiT{
public:
  int max;
  int min;
  struct BiTNode *root;
  BiT(){
    this->max = 0;
    this->min = 0;
    this->root = NULL;
  }
}BiT;

void insert(BiT *T,int key){

  BiTNode *y;
  BiTNode *x;
  BiTNode *z;

  y = NULL;
  x = T->root;
  z = new BiTNode(key);

  while(1){
    if(x == NULL){
      break;
    }
    y = x;
    if(z->key < x->key){
      x = x->left;
    }
    else{
      x = x->right;
    }
  }

  z->parent = y;

  if(y == NULL){
    T->root = z;
  }
  else if(z->key < y->key){
    y->left = z;
  }
  else {
    y->right = z;
  }

  if(T->max < key){
    T->max = key;
  }
  if(T->min > key){
    T->min = key;
  }
}


void inorderTreeWalk(BiTNode *node){

  if(node != NULL){
    inorderTreeWalk(node->left);
    cout << " " << node->key;
    inorderTreeWalk(node->right);
  }
}

void preorderTreeWalk(BiTNode *node){

  if(node != NULL){
    cout << " " << node->key;
    preorderTreeWalk(node->left);
    preorderTreeWalk(node->right);
  }
}

void print(BiT T){

  inorderTreeWalk(T.root);
  cout << endl;
  preorderTreeWalk(T.root);
  cout << endl;
}


int main(){

  int i;
  int n;
  int k;
  BiT T;
  char order[10];

  cin >> n;

  for(i = 0;i < n;i++){
    cin >> order;
    if(strcmp(order,"insert") == 0){
      cin >> k;
      insert(&T,k);
    }
    else if(strcmp(order,"print") == 0){
      print(T);
    }
  }

  return 0;
}

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

int main() {
  int N;
  cin >> N;
  bool ans = false;
  
  for(int i=1;i<10;i++){
    if((N/i < 10) && (N % i == 0)){
      ans = true;
      break;
    }
  }
  
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
    
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

ll n, ed, pw[101010], sum[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    pw[0] = sum[0] = 1;
    for(int i=1; ; i++){
        pw[i] = pw[i-1] * 26;
        sum[i] = sum[i-1] + pw[i];
        if(sum[i] > 1e16){ ed = i; break; }
    }
    
    cin >> n; ll len;
    for(int i=1; i<=ed; i++){
        if(sum[i] > n){
            n -= sum[i-1]; len = i; break;
        }
    }
    for(int i=len-1; ~i; i--){
        for(int j=0; j<26; j++){
            if(n < pw[i]){
                cout << char(j+'a'); break;
            }
            n -= pw[i];
        }
    }
}

Measured memory_bytes: 3612
#include <iostream>
#include <set>
using namespace std;

int main() {
	int N;
	cin >> N;
	int nums[N+1];
	for (int i = 1; i <= N; i++) {
		cin >> nums[i];
	}
	int cur = 1;
	int ct = 0;
	set<int> seen;
	while (cur != 2) {
		if (seen.find(cur) != seen.end()) {
			
			break;
		}

		ct++;
		seen.insert(cur);
		cur = nums[cur];
	}
	if (cur == 2) cout << ct << endl;
	else cout << -1 << endl;
	// cin >> N;

}

Measured memory_bytes: 5376
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main {
	private static void solve(int n, long[][] tasks) {
	  Arrays.sort(tasks, (long[] v1, long[] v2) -> Long.compare(v1[1], v2[1]));
	  long taskSum = 0L;
	  for (int i = 0; i < n; i++) {
	  	long a = tasks[i][0];
	  	long b = tasks[i][1];
	  	taskSum += a;
	  	if (taskSum > b) {
	  	  System.out.println("No");
	  	  return;
	  	}
	  }
	  System.out.println("Yes");
	}
	public static void main (String[] args) throws java.lang.Exception {
	  Scanner sc = new Scanner(System.in);
	  int n = Integer.parseInt(sc.nextLine());
	  long[][] tasks = new long[n][2];
	  for (int i = 0; i < n; i++) {
	  	String[] nums = sc.nextLine().split(" ");
	  	tasks[i][0] = Long.parseLong(nums[0]);
	  	tasks[i][1] = Long.parseLong(nums[1]);
	  }
	  sc.close();
	  solve(n, tasks);
	}
}

Measured memory_bytes: 180724
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }


int n, w, h;
int have[16];
pint pos[16];
int field[16][16], answer[16][16];


bool zero(int id, int x1, int y1, int x2, int y2)
{
  REP(x, x1, x2+1) REP(y, y1, y2+1) if(field[x][y] != 0 && field[x][y] != id) return false;

  return true;
}

int rec(int id)
{
  if(n < id){
    rep(x, w) rep(y, h) answer[x][y] = field[x][y];
    return 1;
  }

  int res = 0;
  
  for(int x1 = pos[id].first; 0 <= x1; x1--) {
    for(int y1 = pos[id].second; 0 <= y1; y1--) {
      REP(x2, pos[id].first, w) REP(y2, pos[id].second, h) if((x2 - x1 + 1) * (y2 - y1 + 1) == have[id]) {
	if(!zero(id, x1, y1, x2, y2)) break;
	
	for(int x = x1; x <= x2; x++) for(int y = y1; y <= y2; y++) field[x][y] = id;

	res += rec(id + 1);

	for(int x = x1; x <= x2; x++) for(int y = y1; y <= y2; y++) if(mp(x, y) != pos[id]) field[x][y] = 0;
      }
    }
  }

  return res;
}

int main()
{
  while(cin >> w >> h >> n && w){

    rep(i, n){
      int b, k;
      cin >> b >> k;
      have[b] = k;
    }

    rep(y, h) rep(x, w){
      cin >> field[x][y];
      pos[field[x][y]] = mp(x, y);
    }

    if(rec(1) == 1) rep(y, h) rep(x, w) cout << answer[x][y] << (x + 1 == w ? "\n" : " ");
    else cout << "NA" << endl;
  }
}

Measured memory_bytes: 1160
#include <iostream>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

struct S {
	mint sum;
	int size;
};

struct F {
	int t;
	int v;
};

mint p10[200001];
mint repunit[200001];	//repunit[5] = 11111

S op(S l, S r) {
	return S{l.sum * p10[r.size] + r.sum, l.size + r.size};
}

S e() { return S{0, 0}; }

S mapping(F f, S s) {
	if (f.t == -1) return s;
	//s.size個のf.vが並んだ数
	return S{repunit[s.size] * f.v, s.size};
}

F composition(F l, F r) {
	if (l.t > r.t) {
		return l;
	}
	return r;
}

F id() { return F{-1, 1}; }

int main() {
	int n, q;
	cin >> n >> q;
	
	vector<S> a(n);
	for (int i = 0; i < n; i++) {
		a[i] = S{1, 1};
	}
	
	p10[0] = 1;
	repunit[0] = 0;
	for (int i = 0; i < n; i++) {
		p10[i + 1] = p10[i] * 10;
		repunit[i + 1] = p10[i] + repunit[i];
	}
	
	lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
	
	for (int i = 0; i < q; i++) {
		int l, r, d;
		cin >> l >> r >> d;
		l--;
		
		//update a[l, r) <- d
		seg.apply(l, r, F{i, d});
		
		//digit sum
		S res = seg.all_prod();
		cout << res.sum.val() << endl;
	}
	return 0;
}

Measured memory_bytes: 12496