akhauriyash/Code-Regression huggingface dataset:
using System.Linq;
using System.Collections.Generic;
using System;

public class P
{
    public int a { get; set; }
    public int e { get; set; }
    public int r { get; set; }
}

public class P2
{
    public int e { get; set; }
    public int time { get; set; }
    public int d { get; set; }
}

public class hello
{
    public static void Main()
    {
        while (true)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var d = int.Parse(line[0]);
            var n = int.Parse(line[1]);
            if (d == 0 && n == 0) break;
            var ps = new P[n];
            for (int i = 0; i < n; i++)
            {
                line = Console.ReadLine().Trim().Split(' ');
                ps[i] = new P { a = int.Parse(line[0]), e = int.Parse(line[1]), r = int.Parse(line[2]) };
            }
            ps = ps.OrderBy(x => x.r).ToArray();
            getAns(d, n, ps);
        }
    }
    static void getAns(int d, int n, P[] ps)
    {
        var map = new int[d + 1, 101];
        for (int i = 0; i < d + 1; i++)
            for (int j = 0; j < 101; j++) map[i, j] = int.MaxValue;
        var q = new Queue<P2>();
        for (int i = 0; i < n; i++)
        {
            if (ps[i].r == 0)
            {
                var nd =d - ps[i].a;
                var ne =         ps[i].e;
                q.Enqueue(new P2 { e = ps[i].e, time = 1, d = d - ps[i].a });
                map[nd, ne] = 1;
            }
            else break;
        }
        while (q.Count() > 0)
        {
            var w = q.Dequeue();
            if (w.d == 0) { Console.WriteLine(w.time); return; }
            for (int i = 0; i < n; i++)
            {
                if (ps[i].r <= w.e)
                {
                    var ne = w.e + ps[i].e;
                    if (ne > 100) ne = 100;
                    var nd = w.d - ps[i].a;
                    if (nd < 0) nd = 0;

                    if ((map[nd, ne] != int.MaxValue && map[nd, ne] > w.time + 1) |
                            (map[nd, ne] == int.MaxValue))
                    {
                        q.Enqueue(new P2 { e = ne, d = nd, time = w.time + 1 });
                        map[nd, ne] = w.time + 1;
                    }
                }
                else break;
            }
        }
        Console.WriteLine("NA");
    }
}



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

int n; string s;
vector<int> v[3];

inline int idx(int b, int a, int i) { //在 v[b] 中寻找第一个不小于 v[a][i] 的下标
	return upper_bound(v[b].begin(), v[b].end(), v[a][i]) - v[b].begin();
}

ll cal(int a, int b, int c) {
    ll ret = 0;
    for (int i = 0; i < v[a].size(); i++) {
        for (int j = idx(b, a, i); j < v[b].size(); j++) {
            for (int k = idx(c, b, j); k < v[c].size(); k++) {
                if (v[b][j] - v[a][i] != v[c][k] - v[b][j]) { //等价于条件中的 j - i != k - j
                    ++ret;
                }
            }
        }
    }
    return ret;
}

int main() {
    cin >> n >> s;
    for (int i = 0; i < n; i++) { //存储不同字母的位置
        if (s[i] == 'R') v[0].push_back(i);
        else if (s[i] == 'G') v[1].push_back(i);
        else v[2].push_back(i);
    }
    ll ans = 0;
    for (int i = 0; i < 3; i++) { //枚举RGB的前后情况
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (i != j && i !=k && j != k) {
                    ans += cal(i, j, k);
                }
            }
        }
    }
    cout << ans;
}


Measured memory_bytes: 3644
import sys
from math import atan, pi

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


def main():
    a, b, x = map(int, readline().split())
    if x > a * a * b / 2:
        angle = atan(2 * (a * a * b - x) / a ** 3)
    else:
        angle = atan(a * b * b / (2 * x))

    print(angle / pi * 180)
    return


if __name__ == '__main__':
    main()


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

bool ansflg;
int idx, n, maxlen;
string s;

int main(){
  while(cin >> s){
    idx = 0;
    n = s.length();
    maxlen = 0;

    while(idx < n){
      bool eggflg = (s[idx] == 'e');
      int len = 0;

      while(idx < n && s[idx] == (eggflg ? 'e' : 'c')){
        if(eggflg) idx += 3;
        else       idx += 7;
        eggflg = !eggflg;
        len++;
      }

      if(maxlen < len){
        maxlen = len;
        ansflg = !eggflg;
      }
    }

    cout << (ansflg ? "egg" : "chicken") << endl;
  }
}

Measured memory_bytes: 0
import fractions as math

n = int(input())
a = list(map(int, input().split()))

ret = 0

l1 = []
l2 = []

t = math.gcd(a[0], a[0])
l1.append(t)

for i in range(1, n):
  t = math.gcd(t, a[i])
  l1.append(t)

t = math.gcd(a[-1], a[-1])
l2.append(t)

for i in range(1, n):
  t = math.gcd(t, a[-1-i])
  l2.append(t)

ret = 0
for i in range(n):
  t = 0
  if i == 0:
    t = l2[-2]
  elif i == n-1:
    t = l1[-2]
  else:
    t = math.gcd(l1[i-1], l2[n-i-2])
  if ret < t:
    ret = t

print(ret)

Measured memory_bytes: 16132
import sys
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n,a,b = map(int,input().split())
v_list = list(map(int,input().split()))

v_list.sort(reverse=True)
max_mean = sum(v_list[:a])/a

number = v_list[a-1]

if v_list[:a].count(number) == a:
    count = 0
    for i in range(a,b+1):
        rest_list = v_list[i:]
        all_num = v_list.count(number)
        rest_num = rest_list.count(number)
        if rest_num > 0 or v_list[i-1] == number:
            count += comb(all_num,rest_num)
    print(max_mean)
    print(count)
else:
    rest_list = v_list[a:]
    all_num = v_list.count(number)
    rest_num = rest_list.count(number)
    print(max_mean)
    print(comb(all_num,rest_num))

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

#define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())

typedef long long ll;
const ll INF = 1LL<<60;
const ll mod = 998244353;
const int MAX_N = 5e5 + 5;
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
vector<ll> prime;

ll inv[MAX_N], fac[MAX_N];

template <class T = ll> T in() { T x; cin >> x; return (x); }
inline ll GCD(ll a, ll b) { ll c; while (b != 0) { c = a % b; a = b; b = c; }return a; }
inline ll LCM(ll a, ll b) { return a * b / GCD(a, b); }
inline ll POW(ll a, ll b) { ll c = 1; while (b > 0) { if (b & 1) { c = a * c%mod; }a = a * a%mod; b >>= 1LL; }return c; }
inline void _nCr() { fac[0] = 1; for (int i = 1LL; i < MAX_N; i++) { fac[i] = fac[i - 1] * i%mod; }for (int i = 0; i < MAX_N; i++) { inv[i] = POW(fac[i], mod - 2); } }
inline ll nCr(ll n, ll r) { return (fac[n] * inv[r] % mod)*inv[n - r] % mod; }
inline void PRI(ll n) { bool A[n + 1]; for (int i = 0; i < n + 1; i++) { A[i] = 1; }for (int i = 2; i < n + 1; i++) { if (A[i]) { prime.pb(i); ll b = i; while (b <= n) { A[b] = 0; b += i; } } } }

vector<vector<pair<int,int>>> Edge;
vector<int> node;

bool bellman_ford(int n,int s) {
	node = vector<int>(n,INF);
	node[s] = 0;
	REP (i,n) {
		REP (j,Edge.size()) {
			REP (k,Edge[j].size()) {
				int from = j,to = Edge[j][k].F;
				int cost = Edge[j][k].S;
				if (node[from] != INF && node[to] > node[from] + cost) {
					node[to] = node[from] + cost;
					if (i == n - 1 && to == n - 1) return true;
				}
			}
		}
	}
	return false;
}

int dp[100000];
int dp2[100000];

signed main() {
	int n;
	cin >> n;
	int a[n];
	int sum = 0;

	REP (i,n) {
		cin >> a[i];
		sum += a[i];
	}
	dp[0] = 1;
	REP (i,n) {
		int ndp[100000];
		REP (j,90005) {
			ndp[j] = dp[j] * 2;
		}
		REP (j,90005) {
			ndp[j + a[i]] += dp[j];
			ndp[j + a[i]] %= mod;
			ndp[j] %= mod;
		}
		REP (j,90005) {
			dp[j] = ndp[j];
		}
	}

	int dim = 0;

	//引きますよ～引クッ
	REP (i,sum + 1) {
		if (i * 2 >= sum) {
			dim += dp[i];
			dim %= mod;
		}
	}

	dim *= 3;
	dim %= mod;
	//引きすぎィ！
	dp2[0] = 1;
	REP (i,n) {
		int ndp[100000];
		REP (j,90005) {
			ndp[j] = dp2[j];
		}
		REP (j,90005) {
			ndp[j + a[i]] += dp2[j];
			ndp[j + a[i]] %= mod;
			ndp[j] %= mod;
		}
		REP (j,90005) {
			dp2[j] = ndp[j];
		}
	}

	if (sum % 2 == 0) {
		dim = dim + mod * 3 - dp2[sum / 2] * 3;
		dim %= mod;
	}

	int ans = (POW(3,n) - dim + 3 * mod) % mod;
	cout << ans << endl;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
#include <sstream>
#include <iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5;
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl

String to integer:
stringstream dark(s);
int x = 0; dark >> x;
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}


ll n, a, b;

void solve()
{
    cin >> n >> a >> b;
    ll k = n/(a+b) * a;
    ll t =n%(a+b);
    k += min(t,a);
    nout(k);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        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() {
int x;
cin >> x;
if(x>=30){
    cout << "Yes" << endl;
}
else{
    cout << "No" << endl;
}

}



Measured memory_bytes: 3556
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define ar array
#define ll long long int

const ll mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a, b, cnt = 0;
        bool ok = false;
        for (int i = 0; i < n; ++i) {
            cin >> a >> b;
            if (a == b) {
                ++cnt;
            }
            else {
                cnt = 0;
            }
            if (cnt == 3) {
                ok = true;
            }
        }
        if (ok) 
            cout << "Yes";
        else
        {
            cout << "No";
        }
        
    }
    

    return 0;
}

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

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

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; }

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int N; cin >> N;
    string S; cin >> S;
    int x = 0;
    int ans = 0;
    REP(i, (int)S.length())
    {
        if(S[i] == 'I') x++;
        else x--;
        chmax(ans, x);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll s;
	cin >> s;
	ll i = sqrtl(s);
	ll j = sqrtl(s);
	i++; j++;
	if (s == 1000000000000000000){
		cout << "0 0 1000000000 0 0 1000000000" << endl;
	} else 
	cout << "0 0 " << i << " " << (i*j)-s << " " << 1 << " " << j << endl;
}

Measured memory_bytes: 256
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n = sc.read();
    let mut a = vec![];
    let mut b = vec![];
    for _ in 0..n {
        a.push(sc.read::<usize>());
        b.push(sc.read::<usize>());
    }

    match (0..n).filter(|&i| a[i] > b[i]).map(|i| b[i]).min() {
        Some(min) => println!("{}", a.iter().sum::<usize>() - min),
        None => println!("0"),
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

using LL = long long;

int main() {
  LL N, K;
  cin >> N >> K;
  vector<LL> A(N);
  for(auto& i: A) cin >> i;

  sort(begin(A), end(A));

  auto ok = [&](auto x) {
    LL k = 0;
    for(int i = 0; i < N; ++i) {
      auto a = A[i];
      int n = 0;
      if(0 <= a) {
        n = upper_bound(begin(A) + i + 1, end(A), x, [&](auto x, auto b) {return x < a * b;}) - begin(A) - i - 1;
        k += n;
      } else {
        n = upper_bound(begin(A) + i + 1, end(A), x, [&](auto x, auto b) {return - x - 1 < -a * b;}) - begin(A) - i - 1;
        k += N - 1 - i - n;
      }
    }
    return K <= k;
  };

  LL l = -1e18-1, h = 1e18+1;
  while(1 < h - l) {
    auto m = (l + h) / 2;
    if(ok(m)) h = m;
    else      l = m;
  }
  cout << h << endl;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>

using namespace std;

constexpr static int MAXN = 2e5;

int64_t n, A, B;
int64_t h[MAXN];

bool check(int64_t m) {
    int64_t extra = 0;
    for (int i = 0; i < n; i++) {
        if (m * B >= h[i])
            continue;
        int64_t added = (h[i] - m * B + (A - B - 1)) / (A - B);
        extra += added;
        if (extra > m)
            return false;
    }
    return true;
}

int main() {
    cin >> n >> A >> B;
    for (int i = 0; i < n; i++)
        cin >> h[i];

    int low = 0, high = 1e9;
    while (low < high) {
        int mid = (low + high) / 2;
        if (check(mid))
            high = mid;
        else
            low = mid + 1;
    }
    cout << low << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{

    long long a,b,c,d;
    string sr;
    map<char,long long>mp;
    map<char,long long>:: iterator it;
    cin>>a;
    while(a--)
    {
        cin>>sr;

        if(sr[0]=='M')
            mp['M']++;

        else if(sr[0]=='A')
            mp['A']++;

        else if(sr[0]=='R')
            mp['R']++;

        else if(sr[0]=='C')
            mp['C']++;

        else if(sr[0]=='H')
            mp['H']++;

    }
    long long arre[6];
    arre[1]=mp['M'];
    arre[2]=mp['A'];
    arre[3]=mp['R'];
    arre[4]=mp['C'];
    arre[5]=mp['H'];
    long long sum=0;
    for(int i=1; i<=3; i++)
    {
        for(int j=i+1; j<=4; j++)
        {
            for(int k=j+1; k<=5; k++)
                sum=sum+arre[i]*arre[j]*arre[k];
        }
    }

cout<<sum;



}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> P;
int n, m, p, K, ans;
const char UDLR[4] = {'U', 'D', 'L', 'R'};
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
char map[52][52], tmp[15];
string patterns[15];
vector<string> pfx;
int next_state[150][4], map_state[52][52][150]; 
bool ng[150];
queue< P > que;


bool check(int x, int y){
    return x>=0&&x<n&&y>=0&&y<m&&map[x][y]!='#';
}


void bfs(){
    memset(map_state, 255, sizeof(map_state));
    int sx, sy, ex, ey;
    for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
        switch (map[i][j]){
            case 'S':
                sx = i;
                sy = j;
                break;
            case 'G':
                ex = i;
                ey = j;
                break; 
            default:
                break;
        }

    while(!que.empty()) que.pop();
    map_state[sx][sy][0] = 0;
    que.push(P(sx*m+sy, 0));

    bool reach=false;
    int tx, ty, tk, xx, yy, kk;
    ans = -1;
    while(!que.empty()){
        tx = que.front().first / m; ty = que.front().first % m; tk = que.front().second; 
        que.pop();
        for(int i=0; i<4; i++){
            kk = next_state[tk][i];
            if(!ng[kk] && check(tx+dx[i], ty+dy[i])){
                // state kk is not forbidden
                xx = tx + dx[i];
                yy = ty + dy[i];
                if(map_state[xx][yy][kk] == -1){
                    map_state[xx][yy][kk] = map_state[tx][ty][tk] + 1;
                    que.push(P(xx*m+yy, kk));
                    if(xx==ex && yy==ey){
                        reach = true;
                        ans = map_state[xx][yy][kk];
                        break;
                    }
                }
            } 
        }
        if(reach) break;
    }
    printf("%d\n", ans);
}


int main(){
    //freopen("in.txt", "r", stdin);
    int k;
    while(scanf("%d %d", &n, &m), n!=0 && m!=0){
        for(int i=0; i<n; i++)
            scanf("%s", map[i]);
        scanf("%d", &p);
        pfx.clear();
        for(int i=0; i<p; i++){
            scanf("%s", tmp);
            patterns[i].assign(tmp);
            for(int j=0; j<=patterns[i].length(); j++)
                pfx.push_back(patterns[i].substr(0, j));
        }
        pfx.push_back(string(""));
        sort(pfx.begin(), pfx.end());
        pfx.erase(unique(pfx.begin(), pfx.end()), pfx.end());
        K = pfx.size();

        for(int i=0; i<K; i++){
            ng[i] = false;
            for(int j=0; j<p; j++){
                ng[i] |= patterns[j].length()<=pfx[i].length() 
                        && pfx[i].substr(pfx[i].length()-patterns[j].length(), patterns[j].length()) == patterns[j];
            }
            for(int j=0; j<4; j++){
                string s = pfx[i] + UDLR[j];
                for(;;){
                    k = lower_bound(pfx.begin(), pfx.end(), s) - pfx.begin();
                    if(k<K && pfx[k]==s) break;
                    s = s.substr(1);
                }
                next_state[i][j] = k;
            }
        }

        bfs();
    }
    return 0;
}


Measured memory_bytes: 4448
#include <bits/stdc++.h>
#define bug(x) cout << #x << " = " << x << endl
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
using namespace std;
typedef long long int ll;
ll q,h,s,d,n,Ti=0,temp;
int main(){
	ios_base::sync_with_stdio(0);
	cin>>q>>h>>s>>d>>n;
	if(n%2){
        temp=min(q*4,min(h*2,s));
        //cout<<temp<<endl;
        Ti=min(n*4*q,min(n*2*h,min(n*s,n/2*d+temp)));
	}
	else{
        Ti=min(n*4*q,min(n*2*h,min(n*s,n/2*d)));
	}
	cout<<Ti<<endl;
	return 0;
}


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

int main(){
	vector<int> a(123456*2+1,1);
	a[0]=0;
	a[1]=0;
	for(int i=0;i<a.size();i++){
		if(a[i]==1){
			for(int j=2*i;j<a.size();j+=i){
				a[j]=0;
			}
		}
	}
	
	//for(int i=0;i<a.size();i++)if(a[i]==1)cout<<i<<" ";
	
	int n;
	while(1){
		cin>>n;
		if(n==0)break;
		int ans=0;
		for(int i=n;i<2*n;i++){
			ans+=a[i+1];
		}
		cout<<ans<<endl;
	}
	return 0;
}

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

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

    int N;
    cin >> N;
    string S;
    cin >> S;
    if (N % 2 != 0) {
        cout << "No" << endl;
    } else {
        bool flag = true;
        for (int i = 0; i < N / 2; i++) {
            if (S[i] != S[N/2 + i]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define TRACE(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cerr << endl;}

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << "[" << *it << " = " << a << "]";
	err(++it, args...);
}

#define MAXN ((int)2e5+5)
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9 + 9)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define LOG(x) if(DEBUG) cerr << x << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<int,int>
#define mid ((l+r)/2)

int x,n;
map <int,int> mp;
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> x >> n;
	for (int i = 0; i < n; ++i)
	{
		int a;
		cin >> a;
		mp[a] = 1;
	}

	if (mp[x])
	{
		int low = x;
		while(mp[low] && low-- > 0);
		int high = x;
		while(mp[high] && high++ < 101);

		cout << ((high-x < x-low) ? high : low) << endl;
	}
	else
	{
		cout << x << endl;
	}

}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

Measured memory_bytes: 3572
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
int main() {
	int n;
	cin >> n;
	int r = n % 10;
	if(r == 3) cout << "bon";
	else if(r == 1 || r == 0 || r == 6 || r == 8) cout << "pon";
	else cout << "hon";
	return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node{
unsigned int key;
struct node *next;
struct node *prev;
};

typedef struct node *NodePointer;
NodePointer nil;
NodePointer listSearch(int key){
NodePointer x=nil->next;
while(x->key!=key){
  if(x==nil)break;
  x=x->next;
  }
  return x;
  }

void init(){
nil=malloc(sizeof(struct node));
nil->next=nil;
nil->prev=nil;
}

void printList(){
  NodePointer np=nil->next;
  int s=1;
  while(1){
    if(np==nil){
      break;
    }
    if(s==0){
      printf(" ");
    }
    printf("%d",np->key);
    np=np->next;
    s=0;
  }
  printf("\n");
  }

void deleteNode(NodePointer np){
  np->prev->next=np->next;
  np->next->prev=np->prev;
  free(np);
  }

void deleteFirst(){
  NodePointer np=nil->next;
  if(np==nil)return;
  deleteNode(np);
  }

void deleteLast(){
  NodePointer x=nil->prev;
  if(x==nil)return;
  deleteNode(x);
  }

void delete(int key){
  NodePointer x;
  x=listSearch(key);
  if(x==nil)return;
  deleteNode(x);
  }

void insert(int key){
  NodePointer np;
  np=malloc(sizeof(struct node));
  np->key=key;
  np->next=nil->next;
  np->prev=nil;
  nil->next=np;
  np->next->prev=np;
  }

int main(){
  int key,n,i,size=0;
  char com[20];
  int nop=0,nod=0;
  scanf("%d",&n);
  init();
  for(i=0;i<n;i++){
    scanf("%s%d",com,&key);
    if(com[0]=='i'){
      insert(key);
      nop++;
      size++;
    }
    else if(com[0]=='d'){
      if (strlen(com)>6){
        if(com[6]=='F')deleteFirst();
        else if(com[6]=='L')deleteLast();
      }else{
        delete(key);
        nod++;
      }
      size--;
    }
  }
  printList();
  return 0;
}



Measured memory_bytes: 32988
#include<stdio.h>
#define N 100000
  
struct sort{
  int number;
  char name;
  int key;
};
  
 struct sort A[N];
  
int Partition(int p, int r){
  int i,j;
  struct sort x,tmp;
  x.number = A[r].number;
  i = p -1;
  for(j = p; j <= r-1; j++){
    if(A[j].number <= x.number){
      i = i + 1;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
  tmp = A[i + 1];
  A[i+1] = A[r];
  A[r] = tmp;
    
  return i + 1;
}
  
void Quicksort(int p, int r){
  int q;
  if(p < r){
    q =  Partition(p, r);
    Quicksort(p, q-1);
    Quicksort(q+1, r);
  }
}
  
  
  
  
  
main(){
  
  int i, l,n,h=0;
  char ch0,ch1,ch2;
  scanf("%d%c",&n,&ch2);
  for(i = 1; i<=n; i++){
    scanf("%c%c%d%c",&A[i].name,&ch0,&A[i].number,&ch1);
    A[i].key = i;
  }
    
  l = Partition(1, n);
  Quicksort(1,n);
  for(i = 1; i <n; i++){
    if(A[i].key > A[i+1].key && A[i].number == A[i+1].number){
      h = 1;
      break;
    }
  }
    if(h!=1){
      printf("Stable\n");
    }
    if(h == 1){
      printf("Not stable\n");
    }
    
  
  for(i = 1; i<=n; i++){
    printf("%c %d\n",A[i].name,A[i].number);
  }
  return 0;
}

Measured memory_bytes: 1780
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int frower[7][2] = {{0,0},{2,380},{3,550},{5,850},{10,1520},{12,1870},{15,2244}};
  int dp[51][7] = {0};
  for(int i=0; i<51; i++){
    for(int j=0; j<7; j++){
      dp[i][j] = 100000;
    }
  }
  for(int i=0; i<51; i++){
    for(int j=1; j<7; j++){
      if(!i){
	for(int k=1;k*frower[j][0]<51;k++){
	  dp[k*frower[j][0]][j] = min(dp[k*frower[j][0]][j],frower[j][1]*k);
	}
      }
      else{
	for(int k=0;i+k*frower[j][0]<51;k++){
	  dp[i+k*frower[j][0]][j] = min(dp[i+k*frower[j][0]][j],dp[i][j-1]+frower[j][1]*k);
	}
      }
    }
  }
  int n;
  while(cin>>n,n){
    for(int i=n/100; i<51; i++){
      if(dp[i][6]){cout <<dp[i][6]<<endl;break;}
    }
  }
  return 0;
}

Measured memory_bytes: 1160
N, M = gets.split.map(&:to_i)
edges = Array.new(N){{}}
M.times do |i|
    a, b = gets.split.map(&:to_i).sort
    edges[a-1][b-1] = true
end

redges = Array.new(N){[]}
N.times do |i|
    ((i+1)...N).each do |j|
        unless edges[i][j]
            redges[i].push(j)
            redges[j].push(i)
        end
    end
end

nums = []
color = []
N.times do |i|
    next if color[i]
    n = [1, 0]
    color[i] = 0
    stack = [i]
    while stack.length > 0
        v = stack.pop
        redges[v].each do |u|
            if color[u]
                if color[v] == color[u]
                    puts -1
                    exit
                end
            else
                color[u] = 1 - color[v]
                n[color[u]] += 1
                stack.push(u)
            end
        end
    end
    nums.push(n)
end

bits = 1
nums.each do |s, t|
    bits = (bits<<s) | (bits<<t)
end

e = 0
N.times do |i|
    if bits[i] == 1
        e = [e, i*(N-i)].max
    end
end
puts N*(N-1)/2 - e

Measured memory_bytes: 18044
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=5e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  ll n,ans=1,t;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> t;
    ans=ans/__gcd(ans,t)*t;
  }
  cout << ans << endl;
}


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

#define rep(l, r) for (int i = (l); i < (r); i++)

typedef long long ll;
 
using namespace std;

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

    int sum = 0;
    rep(0, 2) {
        if (b < a) sum += a--;
        else sum += b--;
    }
    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int h;
	int w;
	int a;
	int b;

	

	for (;;)
	{
		scanf("%d %d", &h, &w);
		if (w==0 && h==0)
		{
			return 0;
		}
		for (b=0;b<h;b++)
		{
			for (a=0;a<w;a++)
			{
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
		
	}

	return 0;
}

Measured memory_bytes: 1000
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //降
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順
#define say(t) cout << (t) << endl;
#define sum_vi(v) accumulate((v).begin(), (v).end(), 0);
#define sum_vll(v)accumulate((v).begin(), (v).end(), 0LL);

int main(){
  string s, t; cin >> s >> t;
  say(t+s);
}

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

int main() {
  int N, alice = 0, bob = 0;
  cin >> N;
  vector<int> a(N);
  for(int i = 0; i < N; ++i) cin >> a.at(i);
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  for(int i = 0; i < N; ++i) {
    if(i % 2 == 0) alice += a.at(i);
    else bob += a.at(i);
  }
  cout << alice - bob << endl;
}


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }
template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	os << v[0];
	for (int i = 1; i < v.size(); i++) os << " " << v[i];
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u; return (is);
}

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


void Main() {
	ll N, M; cin >> N >> M;
	vll S(N), T(M); cin >> S >> T;
	vvll dp(N+1, vll(M+1, 0));
	dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= M; j++) {
			if (j < M && S[i] == T[j]) (dp[i+1][j+1] += dp[i][j]) %= mod;
			if (i < N) (dp[i+1][j] += dp[i][j]) %= mod;
			if (j < M) (dp[i][j+1] += dp[i][j]) %= mod;
			if (i < N && j < M) (dp[i+1][j+1] += mod - dp[i][j]) %= mod;
		}
	}
	ll sum = 0;
	for (int i = 0; i <= M; i++) {
		(sum += dp[N][i]) %= mod;
	}
	cout << sum << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 31616
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int n, k;
	cin >> n >> k;
	
	ll ans = 0LL;
	
	for(ll i = k; i <= n + 1; ++i) {
		ll a = i * (i - 1) / 2;
		ll b = i * n - a;
		ans += (b - a + 1LL);
		ans %= MOD_LL;
	}
	
	cout << ans << endl;
	
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> moti(N);
  rep(i, N) {
    cin >> moti.at(i);
  }
  int tmp = 0;
  
  rep(i, N) {
    for (int j = i+1; j < N ; j++) {
      if (moti.at(i) < moti.at(j)) {
        swap(moti.at(i), moti.at(j));
      }
    }
  }
  
  int ans = 1;
  rep(i, N-1) {
    if (moti.at(i) != moti.at(i+1)) {
      ans++;
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner i=new Scanner(System.in);
		int a=i.nextInt();
		int b=i.nextInt();
		if (a<b) {System.out.println("a < b");};
		if (a>b) {System.out.println("a > b");};
		if (a==b) {System.out.println("a == b");};
	}
}

Measured memory_bytes: 17160
n , g = map(int , input().split())
pt = []
for i in range(0 , n):
	pt.append(list(map(int , input().split())))
# u need to solve all the problems of some bitmask or 
# solve all the problems of the bitmask and if remaining solve the problem which has higher point
# and is not set 
ans = 10**9+89
for i in range(0 , (1<<n)):
	tot , cnt = 0 , 0 
	partial=-1
	for j in range(0 , n):
		if (i & (1<<j)):
			cnt = cnt+pt[j][0]
			tot = tot + (100)*(j+1)*pt[j][0]+pt[j][1]# solve all the problems
		else:
			partial =j# partial solve and take maximum of it because it is optimal
	if tot<g:# if points still remaining
		a = 100*(partial+1)
		rem = (g-tot+a-1)//a
		if rem>=pt[partial][0]:# ignore u can't solve this problem with this set of problems
			continue
		cnt =cnt+rem
	ans = min(ans, cnt)
print(ans)

Measured memory_bytes: 73324
#include <bits/stdc++.h>
using namespace std;
int main(){
	char c;
	cin>>c;
	if(c == 'A')cout<<"T"<<endl;
	if(c == 'T')cout<<"A"<<endl;
	if(c == 'C')cout<<"G"<<endl;
	if(c == 'G')cout<<"C"<<endl;	
	return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807
ll ans = 0;
ll ans2 = 0;
    ll mypow(ll a,ll b){
        ll res=1;
        a%=mo;
        while(b){
            if(b&1)
                res=res*a%mo;
            a=a*a%mo;
            b>>=1;
        }
        return res;
    }
        const int MAX = 510000;
    const int MOD = 1000000007;
    long long fac[MAX], finv[MAX], inv[MAX];

    // テーブルを作る前処理
    void COMinit() {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < MAX; i++){
            fac[i] = fac[i - 1] * i % MOD;
            inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
            finv[i] = finv[i - 1] * inv[i] % MOD;
        }
    }

    // 二項係数計算
    long long COM(int n, int k){
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }
int main()
{
ll n,k;
cin >> n>>k;
    vector<ll> kaij;
    kaij.push_back(1);
    for(ll i = 1; i < k+5; i++){
        kaij.push_back((kaij[i-1]*i)%mo);
    }
COMinit();
rep(i,k){
    ans=COM(n-k+1,i+1);
    ans*=kaij[k-1];
    ans%=mo;
    ans*=mypow((kaij[k-i-1]*kaij[i])%mo,mo-2);
    ans%=mo;
    cout << ans <<endl;
}
return 0;
}


Measured memory_bytes: 12288
s = int(input())
an = [s]
for i in range(1, 1000000):
    if an[i-1]%2==0:
        ins = an[i-1]//2
    else:
        ins = 3*an[i-1]+1

    if ins not in an:
        an.append(ins)
    else:
        print(i+1)
        exit()


Measured memory_bytes: 8776
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll mod= 1e9 + 7;

ll dp[10101][101][2]={};//左からの桁数、modD,数値未満かどうか

int main(){
  string k;
  int D,n;
  cin >>k;
  cin >>D;
  n=k.size();
  dp[0][0][0]=1;

  rep(dgt,n){
    rep(d,D){
      rep(less,2){
        int c=k[dgt]-'0';
        for(int nxt=0;nxt<=(less?9:c);nxt++){//(lessが1なら9,0ならcを返す)
          dp[dgt+1][(d+nxt)%D][nxt<c || less]+=dp[dgt][d][less]%mod;
        }
      }
    }
  }
  cout << (dp[n][0][0]+dp[n][0][1]-1)%mod << endl;
}

Measured memory_bytes: 19424
import java.util.*;

public class Main {

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

		while(sc.hasNext()){
			double[] x = new double[4];
			double[] y = new double[4];
			for(int i=0;i<4;i++){			
				x[i] = sc.nextDouble();
				y[i] = sc.nextDouble();
			}
			
			if(x[0]>x[3] || x[2]>x[1] || y[0]>y[3] || y[2]>y[1]) System.out.println("NO");
			else System.out.println("YES");
		}
	}
}

Measured memory_bytes: 20952
#include <stdio.h>

int main(void) {
    int i;
    int N;
    int S = 0, digit = 0;
    
    scanf("%d", &N);
    int count = N;

    while (count) {
        digit = count % 10;
        S = S + digit;
        count = count / 10;
    }

    if ((N % S) == 0) {
        printf("Yes");
    } else {
        printf("No");
    }

    return 0;
}

Measured memory_bytes: 128
n,k = map(int, input().split())
p = list(map(int, input().split()))

for i in range(n):
    p[i] = (p[i]+1)/2

ans = [0]*(n)
tem = 0
for i in range(n):
    tem = tem
    if i < k:
        tem = tem + p[i]
    else:
        tem = tem + p[i] - p[i-k]
    ans[i] = tem

print(max(ans))


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

typedef long long ll;

int main(){
    int N,W;
    cin>>N>>W;
    vector<ll> w(N);
    vector<ll> v(N);

    for(int i=0; i<N; i++) cin>>w[i]>>v[i];

    vector<vector<ll>> dp(1000,vector<ll>(W+1000,0));

    for(int i=0; i<N; i++){
        for(int sum=0; sum<=W; sum++){
            if(sum - w[i] >= 0){
                dp[i+1][sum] = max(dp[i+1][sum],dp[i][sum-w[i]]+v[i]);
            }
            dp[i+1][sum] = max(dp[i+1][sum],dp[i][sum]);
        }
    }

    cout<<dp[N][W]<<endl;

    return 0;
}

Measured memory_bytes: 793088
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
#define pb push_back

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * g / b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}




const long double PI = 3.14159265359;
const int MAX_N = 100010;

int dp[110][100100];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n; cin >> n;
	int W; cin >> W;
	VE w(n), v(n); rep(i, n)cin >> w[i] >> v[i];
	rep(i, n) {
		for (int j = 0; j <= W; j++) {
			if (j >= w[i]) {
				chmax(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
			}
			chmax(dp[i + 1][j], dp[i][j]);
		}
	}
	cout << dp[n][W] << endl;
	return 0;
}

Measured memory_bytes: 79360
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {   
    int n;
    cin >> n;
    vector<pair<int, int>> vp;
    for (int i = 0; i < n; i++ ) {
        int a, b;
        cin >> a >> b;
        vp.emplace_back(a, b);
    }
    sort(vp.begin(), vp.end());
    cout << vp.back().first + vp.back().second << endl;
}




Measured memory_bytes: 4320
#include <bits/stdc++.h>
using namespace std;
int main(){
 int N,X,T;
 cin>>N>>X>>T;
 
 if(N % X ==0){
  cout<<(N/X)*T<<endl;
 }
 else if(N % X !=0){
  cout<<((N/X)+1)*T<<endl;
 }
}

Measured memory_bytes: 3500
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <string>
#include <vector>
#include <iomanip>
 
using namespace std;
typedef long long ll;
using gra = vector<vector<ll>>;
using gram = vector<unordered_map<ll,ll>>;
 
typedef unsigned long long ull;
 
template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
 
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template <class T> T dup(T a, T b) { return (a + b - 1) / b; }
template <class T> T modpow(T x, T p, T m) { T a=1; while(p){ if(p%2)a =a*x%m; x = x+x%m; p/=2; } return a; }
// template <class T> void prim(T a) { for(ll i=0;i<a.size();++i) { cout << a[i]; } cout << "\n"; }
//template< typename T >
//T mod_pow(T x, T n, const T &p) {
//  T ret = 1;
//  while(n > 0) {
//    if(n & 1) (ret *= x) %= p;
//    (x *= x) %= p;
//    n >>= 1;
//  }
//  return ret;
//}
/////////////////// 
//

#define mod 1000000007LL
#define INF 10000000000000000LL
 
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep1(i, n) for (ll i = 1; i <= n; ++i)
#define rrep(i, n) for (int i = (n - 1); i >= 0; --i)
#define rrep1(i, n) for (int i = n; i > 0; --i)
 
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
//#define modpow(x, p, m) { ll a=1; while(p){ if(p%2)a =a*x%m; x = x+x%m; p/=2; } return a; }
 
#define m0(h) memset(h, 0, sizeof(h))
#define m1(h) memset(h, 1, sizeof(h))
#define m(h, n) memset(h, (n), sizeof(h))
#define all(n) (n).begin(),(n).end()
#define bit(n) (1LL << (n))
#define pb push_back
#define mp make_pair
 
//#ifdef LOCAL
//
//#define dpri(...) fprintf(stderr, __VA_ARGS__)
//#define pria(g) rep(i,g.size()){ cout << i << "{"; rep(j,g[i].size()) cout << g[i][j] << " "; cout << "}" << "\n"; }
//#else
//#define dpri(...) 42
//#define pria(g) 42
//#endif
//
//
//

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ---------------------
  // コーディング開始
  // ---------------------
  int j,k,l;
  cin >> j >> k >> l;
  if(j+k+l >=22) pri("bust");
  else pri("win");
  return 0;
}







Measured memory_bytes: 256
#include <iostream>
#include <string>
#include<cstdlib>
#include <ctype.h>
#include <string.h>
using namespace std;

int main()
{
    char a[50],b[50],c[50];
    cin>>a>>b>>c;
    a[0] = toupper(a[0]);
    b[0] = toupper(b[0]);
    c[0] = toupper(c[0]);
    cout<< a[0] <<b[0]<<c[0]<< endl;
    return 0;
}


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

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  int n,i; cin >> n >> i;

  cout << n-i+1 << endl;
  
  return 0;
}


Measured memory_bytes: 3564
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
#define MAXN 300000
int n;
LL read(){
  LL x=0,F=1;char c=getchar();
  while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
  return x*F;
}
int main()
{
  n=read();
  for(int i=1;i<=9;i++)
    for(int j=1;j<=9;j++)
    if(n==i*j){printf("Yes\n");return 0;}
  printf("No\n");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define pb push_back
#define mod 1e9 + 7;
const int INF = 1e9 + 5;
#define PQ priority_queue<int>
#define pii pair<int, int>
#define ff first
#define ss second


using namespace std;

int main(){

	int n;
	cin>>n;
	vi a(n+1), b(n+1), c(n+1);
	for(int i=0; i<n; i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	int dp[110000][3];
	for(int i=0; i<n; i++){

		for(int j=0; j<3; j++){
			if(i==0){
				if(j==0)dp[i][j]=a[i];
				else if(j==1)dp[i][j]=b[i];
				else if(j==2)dp[i][j]=c[i];
			}



			else{

				for(int k=0; k<3; k++){
					if(j==k)continue;
					if(j==0)dp[i][j] = max(dp[i][j], dp[i-1][k] + a[i]);
					else if(j==1)dp[i][j] = max(dp[i][j], dp[i-1][k] + b[i]);
					else if(j==2)dp[i][j] = max(dp[i][j], dp[i-1][k] + c[i]);
				}




			}
		}

		

	}
	int ans = -1;
	ans = max(ans , dp[n-1][0]);
	ans = max(ans , dp[n-1][1]);
	ans = max(ans , dp[n-1][2]);
	cout<<ans<<endl;



	



	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(1e5) + 5;
constexpr double EPS = 1e-9;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i > 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

int solve(int x){
    ll mul = 1;
    for(int i=2;i*i<=x;i++){
        if(x%i == 0){
            mul *= i;
            if(x/i != i){
                mul *= x/i;
            }
        }
        if(mul >= 2*x)break;
    }
    return mul >= 2*x;
}

int main() {

    int cum[MAX_N]{};
    for(int i=2;i<=100001;i++){
        cum[i] = solve(i);
    }
    for(int i=0;i<=100001;i++){
        cum[i+1] += cum[i];
    }
    int Q;
    cin >> Q;
    for(int i=0;i<Q;i++){
        int n;
        cin >> n;
        cout << cum[n] << endl;
    }
    return 0;
}



Measured memory_bytes: 3492