akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#define INF 10000000
using namespace std;
typedef pair<int,int> P;

int H,W;
char map[100][100];

void grouping(int h,int w,char f);

int main(){
  while(1){
    cin >> H >> W;
    if(H==0&&W==0)break;

    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        cin >> map[i][j];
      }
    }
    int x=0;
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        if(map[i][j]!='.'){
          x++;
          grouping(i,j,map[i][j]);
        }
      }
    }
    cout << x << endl;
  }
}

void grouping(int h,int w,char f){
  map[h][w] = '.';
  if(h-1>=0&&map[h-1][w]==f){
    grouping(h-1,w,f);
  }
  if(h+1<H&&map[h+1][w]==f){
    grouping(h+1,w,f);
  }
  if(w-1>=0&&map[h][w-1]==f){
    grouping(h,w-1,f);
  }
  if(w+1<W&&map[h][w+1]==f){
    grouping(h,w+1,f);
  }
}

Measured memory_bytes: 1632
#include <bits/stdc++.h>
	
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define rev(v) reverse(v.begin(), v.end());
#define io() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(NULL));
	
using namespace std;
	
using ll = long long;
using ld = long double;
using ull = unsigned long long;
	
signed main(){
	io();
	int n; cin >> n;
	vector<int> v(n), cost(n, 0);
	for(auto &x : v) cin >> x;
	for(int i = 0; i < n; ++i){
		if(i > 1){
			cost[i] = min(abs(v[i] - v[i - 1]) + cost[i - 1], abs(v[i] - v[i - 2]) + cost[i - 2]);
		}else if(i == 1){
			cost[i] += abs(v[i] - v[i - 1]);
		}
	}
	cout << cost[n - 1] << '\n';
	return 0;
}

Measured memory_bytes: 3988
N,M = gets.split.map &:to_i

A = gets.split.map &:to_i

A.sort!
b = []
t = nil

M.times{

	if A.size > 0 && (b.size == 0 || A[-1] > b[-1])
		t = A.pop / 2
	else
		t = b.pop / 2
	end

	i = b.bsearch_index{ |x| x >= t}
	if i == nil then
		i = 0
	end
	b.insert(i, t)

}

puts A.inject(0, :+) + b.inject(0, :+)


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

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

const int MAXN = 2e5 + 5;
const int MOD = 998244353;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second 
#define FAIL0 {cout << "0\n"; return 0;}
#define FAIL1 {cout << "-1\n"; return 0;}
#define FAILNO {cout << "No\n"; return 0;}
#define OF {cout << "OVERFLOW!!!\n"; return 0;}

int main(int argc, char **argv) {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int A[3];
    cin >> A[0] >> A[1] >> A[2];
    sort(A,A+3);
    cout << A[0] + A[1] << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define INF 1000000007;
using namespace std;
int main(){
	long long int N;
	long long int ans = 1;
	cin >> N;
	for(int i = 0; i<N; i++){
	ans = ans*(i+1)%INF;
        }
	// ans = ans%INF;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

// i: index, n: size, a: start, b: end
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

// x: container(array, vector etc..)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5

#define PB push_back
#define MP make_pair
#define F first
#define S second

int hp(int x, int p) {
  int value = x - p;
  return value * value;
}

signed main() {
  int n;
  cin >> n;
  int x[100];
  x[0] = 0;
  FOR(i, 1, n) {
    cin >> x[i];
  }

  int min = 0;
  FOR(p, 1, 100) {
    int n_min = 0;
    FOR(i, 1, n) {
      if (p == 1) {
        min += hp(x[i], p);
      } else {
        n_min += hp(x[i], p);
      }
    }
    if (p != 1 && n_min < min) {
      min = n_min;
    }
  }
  cout << min << endl;
  return 0;
}


Measured memory_bytes: 256
n = input()

taro_score = 0
hanako_score = 0
for i in range(n):
    taro_card, hanako_card = map(str, raw_input().split())
    m = min(len(taro_card), len(hanako_card))
    flag = 0
    for j in range(m):
        if taro_card[j] > hanako_card[j]:
            flag = 1
            break
        elif taro_card[j] < hanako_card[j]:
            flag = -1
            break
        elif j == m - 1:
            if taro_card == hanako_card:
                flag = 0
            elif taro_card in hanako_card:
                flag = -1
            elif hanako_card in taro_card:
                flag = 1

    if flag == 1:
        taro_score += 3
    elif flag == -1:
        hanako_score += 3
    else:
        taro_score += 1
        hanako_score += 1

print "%d %d" % (taro_score, hanako_score)

Measured memory_bytes: 6464
words = {""=>0}
gets.to_i.times {
  word = gets.chomp
  if words.include?(word)
    words[word] += 1
  else
     words[word] = 1
  end
}
gets.to_i.times {
  word = gets.chomp
  if words.include?(word)
    words[word] -= 1
  else
     words[word] = -1
  end
}

puts words.max {|x ,y| x[1] <=> y[1]}[1]


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

int partition(int a[],int p,int r){
    int x = a[r];
    int i = p-1;

    for(int j=p;j<=r-1;j++){
        if(a[j]<=x){
            i++;

            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

    int tmp = a[i+1];
    a[i+1] = a[r];
    a[r] = tmp;

    return i+1;
}


int main(){
    int n;
    cin >> n;

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

    int q = partition(a,0,n-1);

    for(int i=0;i<n;i++){
        if(i==q){
            cout << '[' << a[i] << ']';
        }else{
            cout << a[i];
        }

        if(i<n-1){
            cout << " ";
        }else{
            cout << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3452
import java.util.*;
public class Main {
    static PriorityQueue<Long> queue;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int ca = sc.nextInt();
        String str = sc.next();
        int cnt = 0;
        int[] a = new int[n];
        int[] b = new int[n];
        
        for(int i = 0; i<str.length(); i++) {
            char c = str.charAt(i);
            if(c=='o') {
                cnt++;
                a[i] = cnt;
                i += ca;
            }
        }
        if(cnt>k) return;
        for(int i = str.length()-1; i>=0; i--) {
            char c = str.charAt(i);
            if(c=='o') {
                b[i] = cnt;
                cnt--;
                i -= ca;
            }
        }

        for(int i = 0; i<str.length(); i++) {
            if(a[i]==b[i] && a[i]!=0 &&b[i] !=0) System.out.println(i+1);
        }

    }
}

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

count=0
success=True
while True:
    for i in range(N):
        if A[i]%2==1:
            success=False
            break
        else:
            A[i]=int(A[i]/2)
    if success==False:
        break
    count+=1
print(count)

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

using namespace std;
using ll = long long;

#pragma region Macros
#define FOR(i, m, n) for (ll i = (ll)(m); i < (ll)(n); i++)
#define rep(i, n) FOR(i, 0, n)

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

template <class T> string join(const T &v, const string delim = ",")
{
    if (v.empty())
        return "";

    ostringstream res;
    res << v[0];
    for (int i = 1; i < v.size(); i++)
    {
        res << delim << v[i];
    }
    return res.str();
}

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << ":" << #x << " = " << (x) << endl;
#else
#define dbg
#endif

#pragma endregion Macros

int main()
{
    ll A, B, C, K;
    cin >> A >> B >> C >> K;

    ll ans = 0;

    ans += min(A, K);
    K -= A;

    K -= B;

    if(K > 0){
        ans -= K;
    }

    cout << ans << endl;
}


Measured memory_bytes: 3532
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <istream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <climits>
using namespace std;

typedef ostringstream OSS;
typedef istringstream ISS;

typedef vector<int> VI;
typedef vector< VI > VVI;

typedef long long LL;

typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define X first
#define Y second

int main(void) {
	string s;

	while (cin >> s) {
		for (int i = 0; i < (int)s.size(); i++) {
			if (s[i] == '@') {
				int num = s[i + 1] - '0';
				char c = s[i + 2];
				cout << string(num, c);
				i += 2;
			} else {
				cout << s[i];
			}
		}

		cout << endl;
	}

	return 0;
}

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

int main() {
	int n;
	while ( cin >> n ) {
		string s; cin >> s;
		int cnt = 0;
		
		for (char x : s) {
			cnt += ( x == 'R' );
		}
		
		if ( cnt > n/2 ) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}

Measured memory_bytes: 256
def main():
    num = int(input())
    string = input()
    string_list = ['' for i in range(len(string))]
    for i in range(len(string)):
        string_list[i] = (ord(string[i]) - 65 + num) % 26
        string_list[i] = chr(string_list[i] + 65)

    result = ''.join(string_list)
    print(result)





if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int s[11][1111];
int sum(int r1,int c1,int r2,int c2){
	return s[r2+1][c2+1]-s[r2+1][c1]-s[r1][c2+1]+s[r1][c1];
}
bool calc(int mask,int lastcut,int currentcut)
{
	int lastrow=0;
	for(int i=0;i<n;i++)
		if(mask>>i&1||i==n-1){
			int cnt=sum(lastrow,lastcut,i,currentcut);
			if(cnt>k)return false;
			lastrow=i+1;
		}
	return true;
}
int go(int lastcut,int mask)
{
	if(calc(mask,lastcut,m-1))return 0;
	if(!calc(mask,lastcut,lastcut))return 1e9;
	int nowcut=lastcut;
	for(int bit=(1<<15);bit>0;bit>>=1){
		if(nowcut+bit>=m)continue;
		if(!calc(mask,lastcut,nowcut+bit))continue;
		nowcut+=bit;
	}
	return 1+go(nowcut+1,mask);
}
void create2DSs()
{
	for(int i=0;i<=n;i++)
		for(int j=1;j<=m;j++)
			s[i][j]+=s[i][j-1];
	for(int j=0;j<=m;j++)
		for(int i=1;i<=n;i++)
			s[i][j]+=s[i-1][j];
}
void solve()
{
	cin>>n>>m>>k;
	string ser;
	for(int i=0;i<n;i++){
		cin>>ser;
		for(int j=0;j<m;j++)
			s[i+1][j+1]+=ser[j]=='1';
	}
	create2DSs();
	int ans=1e9;
	for(int i=0;i<(1<<(n-1));i++){
		int cnt=go(0,i)+__builtin_popcount(i);
		ans=min(ans,cnt); 
	}
	cout<<ans<<endl;
}
int main()
{
	solve();
	return 0;
}

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

int main(){
  vector<int> a(3);
  cin >> a[0] >> a[1] >> a[2];

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

  if(a[0]==5&&a[1]==5&&a[2]==7) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int floor = 12;
		int room = 10;
		int list[][] = new int[floor][room];
		//0で初期化
		for(int i = 0;i < floor;i++){
			for(int j = 0;j < room;j++){
				list[i][j] = 0;
			}
		}
		int b = 0;
		int f = 0;
		int r = 0;
		int v = 0;
		for(int k = 0;k < n;k++){
			b = sc.nextInt();
			f = sc.nextInt();
			r = sc.nextInt();
			v = sc.nextInt();
			switch(b){
			case 1:
				list[f-1][r-1] += v;
				break;
			case 2:
				list[f+2][r-1] += v;
				break;
			case 3:
				list[f+5][r-1] += v;
				break;
			case 4:
				list[f+8][r-1] += v;
				break;
			}
		}
		for(int i = 0;i < floor;i++){
			for(int j = 0;j < room;j++){
				System.out.print(" " + list[i][j]);
			}
			System.out.println();
			if(i % 3 == 2 && i != (floor - 1)){
				System.out.println("####################");
			}
		}
	}
}


Measured memory_bytes: 29452
S = list(input())
T = input()
candidate = []

ans = True
for i in range(len(S)):
    flag = True
    for j in range(len(T)):
        if i + j >= len(S):
            flag = False
            break
        if S[i+j] == '?' or S[i+j] == T[j]:
            pass
        else:
            flag = False
            break
    if flag:
        candidate.append(i)
        ans = False

if ans:
    print('UNRESTORABLE')
    exit()

i = candidate[-1]
for tmp in range(i, i + len(T)):
    S[tmp] = T[tmp-i]


for i in range(len(S)):
    if S[i] == '?':
        S[i] = 'a'

print(''.join(S))

Measured memory_bytes: 8968
X=int(input())
x=0
ans=[]

if X == 1:
  print(X)
  exit()
else:
  # p
  for i in range(2, int(X**0.5)+1):
    n=1
    a=i
    # b
    while n < X : #超えたら中断
      n *= a
      ans.append(n)
    if n // a > x:
      x = (n//a)
      #print(ans)
print(max(i for i in ans if i <= X))

Measured memory_bytes: 3060
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


import array
import sys


def counting_sort(a, n, k=10000):
    b = array.array("I", (0 for x in range(n)))
    c = array.array("I", (0 for x in range(k + 1)))
    for j in range(0, n):
        c[a[j]] += 1
    for i in range(0, k + 1):
        c[i] += c[i - 1]
    for j in range(n - 1, -1, -1):
        b[c[a[j]] - 1] = a[j]
        c[a[j]] -= 1
    return b


def main():
    n = int(sys.stdin.readline())
    a = array.array("I", map(int, sys.stdin.readline().split()))
    print(" ".join(map(str, counting_sort(a, n))))


if __name__ == "__main__":
    main()

Measured memory_bytes: 161232
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();
		int ans = 0;

		if (A*B <= C*D) {
			ans = C*D;
		} else {
			ans = A*B;
		}

		System.out.println( ans );
	}
}

Measured memory_bytes: 21588
#include<stdio.h>
int main()
{
	int m,n,r,i,j,t,x;
	scanf("%d%d",&m,&n);
	for(r=i=0;i<m;r=r>t?r:t,++i)for(t=j=0;j<n;++j)scanf("%d",&x),t+=x;
	printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 0
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int cnt = 0;
        List<Integer> sortAry = new ArrayList<>();
        int[] ary = new int[n];
        for (int i = 0; i < n; i++) {
            ary[i] = Integer.parseInt(sc.next());
        }
        for (int i = 0; i+2 < n; i++) {
            sortAry.add(ary[i]);
            sortAry.add(ary[i+1]);
            sortAry.add(ary[i+2]);
            Collections.sort(sortAry);
            if (ary[i+1] == sortAry.get(1)) {
                cnt++;
            }
            sortAry.clear();
        }
        System.out.println(cnt);
    }
}

Measured memory_bytes: 21972
#include<iostream>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    int sum=0;
    rep(i,s.size())
    {
        if(s[i]==t[i])sum++;
    }
    cout<<sum<<endl;

    return 0;
}

Measured memory_bytes: 760
#include<bits/stdc++.h>
using namespace std ; 
#define ll long long
typedef pair<ll,ll> pr;
typedef vector<ll> vc;
#define pb push_back
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define reps(i,v) for(ll i=0;i<v.size();i++)
#define test  ll int tcase ; cin>>tcase ; while(tcase--) 
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main(){
    io  ; 
    
        ll int a,b  ;
        cin>>a>>b ; 
        cout<<a*b<<"\n" ; 
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll a[100050];


int main()
{
	int n;
	cin>>n;
	ll sum=0;
	a[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=abs(a[i]-a[i-1]);
	}
	sum+=abs(a[n]);
	for(int i=1;i<=n;i++)
	{
		if(i==1)
		{
			ll tmp=abs(a[1]);
			tmp+=abs(a[2]-a[1]);
			cout<<sum-tmp+abs(a[2])<<endl; 
		}
		else if(i==n)
		{
			ll tmp=abs(a[n]);
			tmp+=abs(a[n]-a[n-1]);
			cout<<sum-tmp+abs(a[n-1]);
		}
		else
		{
			ll tmp=abs(a[i]-a[i-1])+abs(a[i+1]-a[i]);
			cout<<sum-tmp+abs(a[i-1]-a[i+1])<<endl;
		}
	}
	
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
 
ll sum(ll l, ll r) {
  return (l+r)*(r-l+1)/2;
}

int main() {
  int n, k;
  cin >> n >> k;
  mint ans;
  for (int i = k; i <= n+1; ++i) {
    ll l = sum(0, i-1), r = sum(n-i+1, n);
    ans += r-l+1;
  }
  cout << ans << endl;
  return 0;
};

Measured memory_bytes: 3640
#include<stdio.h>
int main(){
    double a,b,c,k;
    double sum=0;
    scanf("%lf %lf %lf %lf",&a,&b,&c,&k);
    if(a<=k){
        sum=sum+a*1;
        k=k-a;
    }else if(k<a){
        sum=k*1;
        printf("%.0f\n",sum);
        return 0;
    }
    if(b<=k){
        sum=sum+0;
        k=k-b;
    }else if((k<b)&&(k!=0)){
        sum=sum+0;
        printf("%.0f\n",sum);
        return 0;
    }
    if(c<=k){
        sum=sum+c*-1;
        k=k-c;
    }else if((k<c)&&(k!=0)){
        sum=sum+k*-1;
        printf("%.0f\n",sum);
        return 0;
    }
    printf("%.0f\n",sum);
}

Measured memory_bytes: 1748
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
namespace mydef {
const int INF = 1ll << 60;
const int MOD = 1e9 + 7;
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
void Yes(bool flag = true) {
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
void No(bool flag = true) {
    Yes(!flag);
}
void YES(bool flag = true) {
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
void NO(bool flag = true) {
    YES(!flag);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
bool dbg = false;
}  // namespace mydef
using namespace mydef;
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<pair<int, int>>
#define vvp vector<vector<pair<int, int>>>
#define pi pair<int, int>
//#define P pair<int, int>
//#define V vector<int>
//#define S set<int>
#define asn ans

int N, x[101010], M, K, a[101010];

void solve() {
    vi memo(N - 1);
    iota(all(memo), 0);
    for (int i = 0; i < M; i++) {
        swap(memo[a[i] - 1], memo[a[i]]);
    }

    vi b(N - 1);
    for (int i = 0; i < N - 1; i++) {
        b[i] = x[i + 1] - x[i];
    }

    vi ans(N - 1);
    iota(all(ans), 0);
    while (K) {
        if (K % 2 == 1) {
            vi tmp(N - 1);
            for (int i = 0; i < N - 1; i++) {
                tmp[i] = ans[memo[i]];
            }
            ans = tmp;
        }
        vi tmp(N - 1);
        for (int i = 0; i < N - 1; i++) {
            tmp[i] = memo[memo[i]];
        }
        memo = tmp;
        K /= 2;
    }

    int A[101010] = {};
    A[0] = x[0];
    for (int i = 0; i < N - 1; i++) {
        A[i + 1] = A[i] + b[ans[i]];
    }

    for (int i = 0; i < N; i++) {
        cout << A[i] << endl;
    }
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x[i];
    }
    cin >> M >> K;
    for (int i = 0; i < M; i++) {
        cin >> a[i];
        a[i]--;
    }

    solve();
    return 0;
}


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

int main(){
  int a,b,k,n=0,hoge;
  cin >> a >> b >> k;
  if(a>=b){
    hoge=a;
  }else{
    hoge=b;
  }
  int i=hoge;
  int ans;
  while(n!=k){
    if(a%i==0 && b%i==0){
      n++;
    }
    if(n==k){
      ans=i;
    }
    i--;
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

A, B, C, D = nl()

c_total = B // C - (A - 1) // C
d_total = B // D - (A - 1) // D

CD = lcm(C, D)
cd_total = B // CD - (A - 1) // CD

print(B - A + 1 - (c_total + d_total - cd_total))


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

int N;
vector<int> p;

int main(void){
  cin >> N;
  p.resize(N);
  int i,sum=0;
  REP(i,N){
    cin >> p[i];
    sum += p[i];
  }
  sort(p.begin(),p.end());
  sum -= p[N-1]/2;
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

from collections import defaultdict, deque


def initialize_maze(h, w):
    grid = dict()

    for x in range(w + 2):
        grid[(x, 0)] = "#"
        grid[(x, h + 1)] = "#"

    for y in range(h + 2):
        grid[(0, y)] = "#"
        grid[(w + 1, y)] = "#"

    return grid


def main():
    def bfs():
        que = deque()
        que.append((1, 1, 0))

        while que:
            x, y, count = que.popleft()
            for mx, my in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                nx, ny = x + mx, y + my
                if grid[(nx, ny)] == ".":
                    que.append((nx, ny, count + 1))
                    grid[(nx, ny)] = "!"
                elif grid[(nx, ny)] == "G":
                    min_count = count + 1
                    return min_count
        return - 1

    h, w = map(int, readline().split())
    grid = initialize_maze(h, w)

    black_num = 0
    for y in range(1, h + 1):
        s = input()
        for x, state in enumerate(s, 1):
            grid[(x, y)] = state
            if state == "#":
                black_num += 1

    grid[(w, h)] = "G"

    grid[(1, 1)] = "!"
    min_count = bfs()

    if min_count == -1:
        print(-1)
    else:
        print(h * w - black_num - min_count - 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 40432
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    long long int candy, gives[10010];
    int ans = 0;

    cin >> n >> candy;

    for (int i = 0; i < n; i++) {
        cin >> gives[i];
    }

    sort(gives, gives+n);

    for (int i = 0; i < n; i++) {
        if (gives[i] <= candy && i < n-1) {
            ans++;
            candy -= gives[i];
        }
        else if (i == n-1 && candy == gives[i]) {
            ans++;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll ans=n*(n*n+3*n+2)/6;
    rep(i,n-1){
        ll u,v;
        cin>>u>>v;
        u--,v--;
        if(u>v) swap(u,v);
        ans-=(u+1)*(n-v);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;

int main()
{
    string s;
    char a='0',b='0';
    int cnta=0,cntb=0;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(a=='0')
            a=s[i];
        else if(b=='0'&&a!=s[i])
            b=s[i];

        if(a==s[i])
            cnta++;
        else if(b==s[i])
            cntb++;
    }
    if(cnta==2&&cntb==2)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e15;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

vll G[100005];

ll ng;
bool reachable[100005];
void dfs(ll v, ll p){
  reachable[v]=true;
  for(auto nv: G[v]){
    if(nv==p) continue;
    if(nv==ng) continue;
    dfs(nv,v);
  }
}

ll dist[100005];
void dfs2(ll v, ll p, ll cost){
  dist[v]=cost;
  for(auto nv: G[v]){
    if(nv==p) continue;
    dfs2(nv,v,cost+1);
  }
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,u,v; cin>>n>>u>>v; u--,v--;
  
  rep(i,n-1){
    ll a,b; cin>>a>>b; a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  queue<pll> q;
  q.emplace(u,-1); q.emplace(v,-1);
  vb visited(n);
  while(!q.empty()){
    auto pi=q.front(); q.pop();
    ll v=pi.first, p=pi.second;
    bool flg=false;
    for(auto nv: G[v]){
      if(nv==p) continue;
      if(visited[nv]){
        ng=nv;
        flg=true;
        break;
      }
      visited[nv]=true;
      q.emplace(nv,v);
    }
    if(flg) break;
  }
  
  dfs(u,-1);
  dfs2(v,-1,0);
  ll ans=0;
  rep(i,n){
    if(reachable[i]){
      chmax(ans,dist[i]-1);
    }
  }
  cout<<ans<<endl;
  
  
}

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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)
#define all(a) a.begin(), a.end()

using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvb = vector<vb>;

constexpr int MOD = 1000000007;

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

    int n;
    cin >> n;

    int ans = 0;
    vi b(n + 1, INT_MAX);
    rep(i, 0, n - 1) {
        cin >> b[i + 1];
        ans += min(b[i], b[i + 1]);
    }
    cout << ans + min(b[n - 1], b[n]) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	string s1;
	cin>>s1;
	
	int i,t=0;
	for(i=0;i<s.size();i++)
	{
		if(s[i]!=s1[i])
		{
			t=1;
			break;
		}
		
	}
	if(t==1)
	cout<<"No";
	else
	{
		if(s.size()<s1.size())
		cout<<"Yes";
	}
}


Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
  while(1){
    int t,n,len;
    string str;
    cin >> t >> str;
    if(t==0) break;
    len = str.length();
    n = atoi(str.c_str());
    
    int ans=0;
    int idx=-1;
    bool rej=false;
    for(int i=0; i<(1<<(len-1)); i++){
      int num=n;
      int sum=0;
      for(int j=len-1; j>0; j--){
        if((i & 1<<(j-1)) != 0){
          int d = num/pow(10,j);
          sum += d;
          num -= d*pow(10,j);
        }
      }
      sum+=num;
      if(sum<=t){
        if(ans==sum){
          rej=true;
        }else if(sum > ans){
          ans = sum;
          idx=i;
          rej=false;
        }
      }
    }
    if(rej){
      cout << "rejected" << endl;
      continue;
    }
    if(ans==0){
      cout << "error" << endl;
      continue;
    }
    cout << ans << " ";
    for(int j=len-1; j>0; j--){
      if((idx& 1<<(j-1)) != 0){
        int d = n/pow(10,j);
        cout << d << " ";;
        n -= d*pow(10,j);
      }
    }
    cout << n << endl;
  }
  return 0;
}

Measured memory_bytes: 3228
import sys,heapq,bisect

mod = 10**9+7

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return input()

def GCD(a,b):
    while(a%b != 0):
        a,b = b,a%b
    return b

def LCM(a,b):
    return a*b//GCD(a,b)

def main():
    N = I()
    S1 = S()
    S2 = S()

    r = 1
    d_type = 0
    i = 0

    if S1[0] == S2[0]:
        r *= 3
        i += 1
        d_type = 0
    else:
        r *= 3 * 2
        i += 2
        d_type = 1

    while i < N:
        if d_type == 0 and S1[i] == S2[i]:
            r *= 2
            r %= mod
            d_type = 0
            i += 1
        elif d_type == 1 and S1[i] == S2[i]:
            d_type = 0
            i += 1
        elif d_type == 0 and S1[i] != S2[i]:
            r *= 2
            r %= mod
            d_type = 1
            i += 2
        else:
            r *= 3
            r %= mod
            d_type = 1
            i += 2

    return(r)

if __name__ == "__main__":
    print(main())

Measured memory_bytes: 3064
#include<stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
 
 
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//pair sort
bool compare_by_b(pair<LL, LL> a, pair<LL, LL> b) {
    if(a.second != b.second) return a.second < b.second;
    else return a.first < b.first;
}
std::uint32_t euclidean_gcd(std::uint32_t a, std::uint32_t b){return b != 0 ? euclidean_gcd(b, a % b) : a;}


void solve(std::string S){
    int ans=0;
    REP(i, S.size()/2){
        if(S[i]!=S[S.size()-1-i])ans++;
    }
    cout<<ans<<endl;return;
}

int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
def solve(s, k):
    mapping = {(chr(ord("a") + i)): (26-i)%26 for i in range(26)}
    t = list(s)
    n = len(s)
    for i in range(n):
        if k >= mapping[s[i]]:
            t[i] = "a"
            k -= mapping[s[i]]
    if k > 0:
        k %= 26
        j = ord(t[i]) + k
        if j > ord("z"):
            j -= 26
        t[n-1] = chr(j)
    return "".join(t)

s = input()
k = int(input())
print(solve(s, k))

Measured memory_bytes: 4084
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define pvec(vec) {for (auto v: vec) cout << v << ' '; cout << endl;}
#define pivec(vec) {rep(i, 0, vec.size()) cout << i << ':' << vec[i] << ' '; cout << endl;}

using namespace std;
using ll = long long;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> heights(n);
    rep(i, 0, n) cin >> heights[i];
    vector<bool> good(n, true);
    rep(i, 0, m)
    {
        int a, b;
        cin >> a >> b;
        --a, --b;
        if (heights[a]>heights[b])swap(a, b);
        if (heights[a] == heights[b])
            good[a] = good[b] = false;
        else
            good[a] = false;
    }

    int cnt = 0;
    rep(i, 0, n)
    if (good[i]) ++cnt;
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3788
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
map<ll,ll> mp;
ll a,ans;
void solve()
{
    ans=0;
    rep(i,a)
    {
        ll b;
        cin>>b;
        mp[b]++;
    }
    for(map<ll,ll>::iterator it=mp.begin();it!=mp.end();it++)
    {
        if(it->first<=it->second)ans+=it->second-it->first;
        else ans+=it->second;
    }
}
main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>a;
    solve();
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6272
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = 1000000007;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;
	final int LEN = 0;

	void doIt() {
		int x = sc.nextInt();
		boolean dp[] = new boolean[x + 1];
		Arrays.fill(dp, false);
		dp[0] = true;
		for(int i = 100; i <= 105; i++) {
			for(int j = i; j <= x; j++) {
				if(dp[j - i])dp[j] = true;
			}
		}
		System.out.println(dp[x]?1:0);
	}

	public static void main(String[] args) {
		new Main().doIt();
	}
}


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

using namespace std;

const int MAXN = 5000 + 10;
const long long INF = (long long)(1e15);

struct Box {
    int w, s;
};

int n;
Box a[MAXN];
long long f[MAXN][MAXN];

bool cmp(Box &a, Box &b) {
    return a.w + a.s < b.w + b.s;
}

void minmize(long long &a, long long b) {
    a = min(a, b);
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i].s >> a[i].w;
    
    sort(a + 1, a + n + 1, cmp);
    
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= n; ++j)
            f[i][j] = INF;
    f[0][0] = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j <= i; j++)
            if (f[i][j] < INF) {
                // not put i+1
                minmize(f[i + 1][j], f[i][j]);
                
                // put i+1
                if (a[i + 1].s >= f[i][j])
                    minmize(f[i + 1][j + 1], f[i][j] + a[i + 1].w);
            }
    int res = 0;
    for(int i = 0; i <= n; ++i)
        if (f[n][i] < INF)
            res = i;
    
    cout << res << "\n";
}

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

typedef long long ll;
#define MAXN 100010
const int mod = 1e9 + 7;
const int INF = 1e9 + 10;

char s[MAXN];

bool check(int n, int k)
{
    if (k == 1) return true;
    if (n >= 2 * k) return true;
    
    int cur = 0;
    for (int i = 1; i <= k; ++i)
    {
        int x = s[i] - '0';
        x ^= cur;
        if (x == 1)
        {
            if (i + k - 1 > n) return false;
            cur ^= 1;
        }
    }
    return true;
}

int main()
{
    int n;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    
    int l = 1, r = n, mid;
    while (l < r)
    {
        mid = (l + r + 1) >> 1;
        if (check(n, mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int T, n, m, x, y, z;
ll dp[41][2][1<<17];
const int mask = (1 << 17) - 1;
int main(int argc, char *argv[]){
	ios::sync_with_stdio(false);
	cin >> n >> x >> y >> z;
	y += z;
	x += y;
	dp[0][0][1] = 1;
	REP(i, n) REP(f, 2) REPS(j, 10)if (i || j) {
		REP(b, 1 << 17) if(dp[i][f][b]){
			int nxtb = (b << j) + 1;
			int nxtf = f || (((nxtb >> x) & 1) && ((nxtb >> y) & 1) && ((nxtb >> z) & 1));
			dp[i + 1][nxtf][nxtb & mask] = (dp[i + 1][nxtf][nxtb & mask] + dp[i][f][b]) % MOD;
		}
	}
	ll ans = 0;
	REP(b, 1 << 17) ans += dp[n][1][b];
	cout << ans % MOD << endl;
	return 0;
}


Measured memory_bytes: 73472
#include <stdio.h>
#include <math.h>


int main(void){
  
  int n, i;
  int a, b, c;

  scanf("%d", &n);
  for(i = 0;i < n; i++){
      scanf("%d %d %d", &a, &b, &c);
      if((a*a + b*b == c*c)|| (b*b + c*c == a*a) || (c*c + a*a == b*b)) printf("YES\n");
      else printf("NO\n");
  }
  return 0;
  
}
  

Measured memory_bytes: 580
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

using namespace std;

/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
*/

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

/*
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()
*/

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-9;

void solve() {
    ll n;
    cin >> n;
    vll w(n), s(n), v(n);
    vpll p(n);
    ll swmax = 0;
    for(ll i = 0; i < n; i++) {
        cin >> w[i] >> s[i] >> v[i];
        p[i] = make_pair(w[i] + s[i], i);
        chmax(swmax, s[i] + w[i]);
    }
    sort(p.begin(), p.end());
    vvll dp(n + 1, vll(swmax + 1));
    for(ll i = 0; i < n; i++) {
        int idx = p[i].second;
        for(ll j = 0; j <= swmax; j++) {
            dp[i + 1][j] = dp[i][j];
            if(j - w[idx] <= s[idx] && j >= w[idx]) {
                chmax(dp[i + 1][j], dp[i][j - w[idx]] + v[idx]);
            }
        }
    }
    ll ans = 0;
    for(ll i = 0; i <= swmax; i++) chmax(ans, dp[n][i]);
    cout << ans << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


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

const int INF = 1e9 + 7;
using namespace std;
using ll = long long;
int main(int argc, char const *argv[]) {
    int n, k;
    cin >> n >> k;
    vector<ll> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    vector<ll> dp(n, INF);
    dp[0] = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < min(i, k) + 1; j++) {
            dp[i] = min(dp[i], dp[i - j] + abs(h[i - j] - h[i]));
        }
    }
    cout << dp[n - 1] << "\n";
    return 0;
}


Measured memory_bytes: 4820
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

typedef long long ll;


int main(){
  int n;
  scanf("%d", &n);
  int ans=0;
  vector<pair <int, int> > v;
  rep(i,n){
    int t;
    scanf("%d", &t);
    v.push_back(make_pair(t,i));
  }
  sort(v.begin(),v.end());
  rep(i,n){
    if(i%2&&!(v[i].second%2)) ans++;
  }
  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 1400
#include<stdio.h>
int main(void){
    int i,j,k,l,t,h[5],n;

    scanf("%d",&n);
    for(i=0;i<n;i++){

        for(j=0;j<3;j++){
        scanf("%d",&h[j]);
        }
        for(k=0;k<2;k++){
            for(l=k+1;l<3;l++){
                if(h[k]<h[l]){
                    t=h[k];
                    h[k]=h[l];
                    h[l]=t;
                }
            }
        }
        if(h[0]*h[0]==h[1]*h[1]+h[2]*h[2]){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
    return 0;
}

Measured memory_bytes: 580
N,K = list(map(int,input().split()))
A = []
for i in range(K):
    d = int(input())
    a = list(map(int,input().split()))
    for j in a:
        A.append(j)
ans = 0
for i in range(1,N+1):
    if not i in A:
        ans += 1
print(ans)

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

#intの場合
N ,M = map(int,input().split())

intlist = list(map(int, input().split()))
newlist = sorted(intlist, reverse=True)[:M]

if newlist[M-1] >= ( sum(intlist) / (4 * M)):
  print ("Yes")
else:
  print ("No")


Measured memory_bytes: 2940