akhauriyash/Code-Regression huggingface dataset:
n, W = map(int,input().split())
items = [[0,0] for _ in range(n+1)]
for i in range(n):
    items[i+1] = list(map(int, input().split()))

dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    weight, value = items[i][0], items[i][1]
    for w_limit in range(1,W+1):
        if w_limit - weight >= 0:
            dp[i][w_limit] = max(dp[i-1][w_limit], dp[i-1][w_limit-weight] + value)
        else:
            dp[i][w_limit] = dp[i-1][w_limit]
print(dp[n][W])

        

Measured memory_bytes: 146716
#include<bits/stdc++.h>
using namespace std;
int main()
{
	multiset<int> answer;
	int n,k; cin>>n;
	for(int i =0 ; i < n ; i++)
	{
		cin>>k;
		auto it = answer.lower_bound(k);
		if(it==answer.begin())
			 answer.insert(k);
		else
		{
			it--;
			answer.erase(it);
			answer.insert(k);
		}
	}
	cout<<answer.size()<<endl;
	return 0;
}

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

int main() {
  int a, b; cin >>a >>b;
  string win;
  
  if (a==b) win = "Draw";
  else if (a==1) win = "Alice";
  else if (b==1) win = "Bob";
  else if (a>b) win = "Alice";
  else win = "Bob";
  
  cout <<win <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define y1 cgbngfgn
#define pb push_back
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fir first
#define m_p make_pair
#define sec second
#define files(name) freopen(name".dat","r",stdin); freopen (name".sol","w",stdout);
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#define time pdojegoritg
typedef long long ll;
typedef long double ld;
const int arr=500000;
short int dp[5010][5010];
signed main()
{
    int a,b;
    cin>>a>>b;
    cout<<(a+b+1)/2<<'\n';

}


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

class Edge
{
	public:
	int to,cost;
	Edge(int t,int c)
	{
		to=t;cost=c;
	}
};

vector<Edge> g[10000];
vector<int> tres; //トポロジカルソートの結果
//tres[j]=h 頂点hはトポロジカルソートするとj番目の意
bool used[10000];

//再帰で頂点を訪れる（現在nowにいる）
void visit(int now)
{
	used[now]=true;
	for(int i=0;i<g[now].size();i++)
	{
		//まだ訪れていなければ再帰
		if(!used[g[now][i].to])
			visit(g[now][i].to);
	}
	tres.push_back(now);
	return;
}
//n頂点のトポロジカルソート
void tsort(int n)
{
	tres.clear();
	fill(used,used+10000,false);//初期化
	for(int i=0;i<n;i++)
	{
		if(!used[i])
			visit(i);
	}
	//これをやると逆順になっているのでひっくり返す
	reverse(tres.begin(),tres.end());
}

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int s,t;
		cin>>s>>t;
		g[s].push_back(Edge(t,1));
	}
	tsort(n);
	for(int i=0;i<n;i++)
		cout<<tres[i]<<endl;
}


Measured memory_bytes: 3960
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <memory.h>
#include <algorithm>
#include <cassert>
#include <numeric>
#include <functional>
#include <queue>

using namespace std;

#define prev prev_______________________
#define next next_______________________
#define hash hash_______________________
#define y1 y1___________________________

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define all(c) (c).begin(), (c).end()
#define sz(c) int((c).size())
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define fst first
#define snd second

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#ifdef LOCAL
#define eprintf(args...) fprintf(stderr, args), fflush(stderr);
#else
#define eprintf(args...) ;
#define cerr if (0) cerr
#endif

int n;
vi a;

bool read() {
    if  (!(cin >> n)) {
        return 0;
    }
    a.resize(n);
    forn(i, n) {
        cin >> a[i];
    }
    return 1;
}

vector<pll> get_dp() {
    vll pref(n + 1);
    forn(i, n) {
        pref[i + 1] = pref[i] + a[i];
    } 

    set<ll> prefs;
    vector<pll> dp(n + 1, mp(-1, -1));
    for (int len = 2; len <= n; ++len) {
        prefs.insert(pref[len - 1]);

        const ll S = pref[len];
        const ll want = S / 2;
        auto it = prefs.upper_bound(want);
        if  (it != prefs.begin()) {
            --it;
        }
        assert(it != prefs.end());
        ll best_pref = *it;
        forn(iter, 3) {
            ll cur_pref = *it;
            if (abs(cur_pref - (S - cur_pref)) < abs(best_pref - (S - best_pref))) {
                best_pref = cur_pref;
            } 
            ++it;
            if  (it == prefs.end()) {
                break;
            }
        }
        assert(best_pref <= S);
        dp[len] = mp(best_pref, S - best_pref);
    }

    return dp;
}

const ll INF = 1e18;

void solve() {
    auto pref_dp = get_dp();

    reverse(all(a));
    auto suff_dp = get_dp();
    reverse(all(a));

    ll best = INF;
    for (int len = 2; len + 2 <= n; ++len) {
        ll b = pref_dp[len].fst;
        ll c = pref_dp[len].snd;
        ll d = suff_dp[n - len].fst;
        ll e = suff_dp[n - len].snd;

        assert(b != -1);
        assert(d != -1);

        eprintf("%lld %lld %lld %lld\n", b, c, d, e);

        ll mn = min(min(b, c), min(d, e));
        ll mx = max(max(b, c), max(d, e));
        ll cur = mx - mn;
        assert(cur >= 0);
        best = min(best, cur);
    }

    cout << best << endl;
}

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

#ifdef LOCAL
    #define FNAME "a"
    freopen(FNAME ".in", "r", stdin);
    freopen(FNAME ".out", "w", stdout);
#endif

    while (read()) {
        solve();

        eprintf("\n");
    }

    return 0;
}



Measured memory_bytes: 18276
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef long double ld;
typedef unsigned long long ull;
#define X first
#define Y second
#define mp make_pair
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class X> using indexed_map = tree<T, X, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int M = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int modpow(int n, int k, int MOD);
 
/**************** code starts here ****************/
 
void poppingfever() {
  int n; cin >> n;
	string s; cin >> s;
	int r = 0, b = 0;
	for (char c: s) {
		if (c == 'R') r++; else b++;
	}
	if (r > b) cout << "Yes"; else cout << "No";
}
 
/**************************************************/
 
signed main() {
	#ifdef fastfurioustransform
	freopen("inp.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
 
	ios::sync_with_stdio(0); cin.tie(0);
	//cout << fixed << setprecision(12);
 
	poppingfever();
 
	return 0;
}
 
int modpow(int n, int k, int MOD) {
	int ans = 1; n %= MOD;
	while (k > 0) {
		if (k & 1) ans = (ans*n) % MOD;
		k >>= 1; n = (n*n) % MOD;
	}
	return ans; 
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();


		if (A>=6 && A<=12) B/=2;
		else if (A<=5) B=0;

		System.out.println(B);
	}

}

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

int main() {

  int a,b,c,p,x,k;

cin >> a >>  b ;

	p=a*b;
	x=p%2;
	if(x==1){
	cout << "Odd"<< endl;
	}
	if(x==0){
	cout << "Even"<< endl;
	}

}

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
typedef unsigned long long ll;

int main(){
    ll n;
    cin >> n;
    vector<ll> x(n, 0);
    REP(i, n) cin >> x[i];

    vector<ll>cpy = x;
    sort(ALL(cpy));

    REP(i, n){
        if (x[i] < cpy[n/2]){
            cout << cpy[n/2] << endl;
        }
        else{
            cout << cpy[n/2-1] << endl;
        }
    }
}

Measured memory_bytes: 6308
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < int(n); ++i)
#define REPE(i, a, b) for (int i = (a); i <= int(b); ++i)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define EB emplace_back
using LL = long long;
using PII = pair<int, int>;
#define F first
#define S second

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  REPE(i, 0, n) REPE(j, 0, m) {
    if (n * m - i * j - (n - i) * (m - j) == k) {
      puts("Yes");
      return 0;
    }
  }
  puts("No");
  return 0;
}



Measured memory_bytes: 256
from collections import Counter
N = int(input())
blue_cards = Counter(input() for _ in range(N))
M = int(input())
red_cards = Counter(input() for _ in range(M))
ans = 0
for blue_word, blue_count in blue_cards.items():
    tmp_ans = blue_count
    if blue_word in red_cards.keys():
        tmp_ans -= red_cards[blue_word]
    if tmp_ans > ans:
        ans = tmp_ans
print(ans)



Measured memory_bytes: 3316
n = int(input())
a= list(map(int,input().split()))
c = 1
if 0 in a:
    print(0)
else:
    for x in a:
        if x >10**18:
            print(-1)
            break
        else:
            c*=x
            if c >10**18:
                print(-1)
                break
    else:
        print(c)

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

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

    int sum;
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
    int m = (int)round(sum / (double)n);

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (a[i] - m) * (a[i] - m);
    }

    cout << ans << endl;
}


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

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b){
	if(a < b)swap(a,b);
	ll r = a%b;
	while(r!=0){
		a=b;
		b=r;
		r=a%b;
	}
	return b;
}

int main(){
	int n; 
	cin >> n;
	ll ans;
	for(int i = 0; i < n; i++){
		ll nn; 
		cin >> nn;
		if(!i)ans = nn;
		else ans = gcd(ans, nn);
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

void print_edge(int n) {
    if (n % 2 == 1) {
        FOR(i, 1, n) cout << i << " " << n << endl;
        if (n > 3) print_edge(n - 1);
        return;
    }
    FOR(i, 1, n) {
        FOR(j, i + 1, n + 1) {
            if (i + j != n + 1) cout << i << " " << j << endl;
        }
    }
}

int main() {
    int N;
    cin >> N;
    cout << (N * (N - 1)) / 2 - N / 2 << endl;
    print_edge(N);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#define DOT '.'

using namespace std;

int h, w, cl, sp;
vector<string> data;

void insert(const string& s){
  int i=0;
  while(i+w<s.size()){
    data.push_back(s.substr(i,w));
    i+=w;
  }
  data.push_back(s.substr(i) + string(i+w-s.size(),DOT));
}

void print(){
  const string SP1(w,DOT), SP2(sp,DOT);
  int tmp=data.size();
  if(tmp%(h*cl)){
    for(int i=0; i<h*cl-tmp%(h*cl); ++i) data.push_back(SP1);
  }
  for(int k=0; k<data.size()/(h*cl); ++k){
    for(int i=0; i<h; ++i){
      for(int j=0; j<cl; ++j){
	cout << data[i+h*j+h*cl*k] << (j==cl-1 ? "\n" : SP2);
      }
    }
    printf("#\n");
  }
  printf("?\n");
}

int main(){
  string s;
  bool end=false;
  while(1){
    data.clear();
    for(int i=0; ; ++i){
      getline(cin, s);
      if(i<4){
	int x = atoi(s.c_str());
	if(i==0 && x==0){ end=true; break; }
	if(i==0) h=x;
	if(i==1) cl=x;
	if(i==2) w=x;
	if(i==3) sp=x;
	continue;
      }
      if(s=="?") break;
      insert(s);
    }
    if(end) break;
    print();
  }
  return 0;
}

Measured memory_bytes: 1224
using System;
using System.Linq;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            var b = Console.ReadLine();
            string[] a1 = new string[] { "A", "C", "G", "T" };
            string[] a2 = new string[] { "T", "G", "C", "A" };

            for (int i = 0; i < 4; i++)
            {
                if (a1[i] == b)
                {
                    Console.WriteLine(a2[i]);
                    break;
                }
            }
        }
    }
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  int alice = 0;
  int bob = 0;

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


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

h, w, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
CC = [[] for i in range(h)]
for i in range(m):
    CC[C[i][0]-1].append(C[i][1]-1)

for i in range(h):
    CC[i].sort()

A = [0] * h
B = [0] * w
for i in range(m):
    A[C[i][0]-1] += 1
    B[C[i][1]-1] += 1

# ans = 0
# for i in range(m):
#     ans = max(ans, A[C[i][0]-1] + B[C[i][1]-1] - 1)

D = [[A[i], i] for i in range(h)]
E = [[B[i], i] for i in range(w)]
D.sort(reverse=True)
E.sort(reverse=True)

# print(D,E)

from bisect import bisect
if not ([D[0][1]+1, E[0][1]+1] in C):
    # print("r1")
    ans = D[0][0] + E[0][0]
else:
    ans = 0
    aa = D[0][0] + E[0][0]
    co = 0
    F = []

    for i in range(h):
        for j in range(w):
            if D[i][0] + E[j][0] == aa:
                F.append([D[i][1], E[j][1]])
                co += 1
            else:
                break
        # if co > m:
        #     break
    # if co > m:
    #     # print("r2")
    #     ans = D[0][0] + E[0][0]
    else:
        ha = 0
        # print(F)
        # print(CC)
        for i in range(len(F)):
            ind = bisect(CC[F[i][0]], F[i][1])
            if ind==0 or (ind >= 1 and CC[F[i][0]][ind-1] != F[i][1]):
                # print(CC[ind-1], F[i][1])
                ha = 1
                break
        if ha == 1:
            # print("r3")
            ans = D[0][0] + E[0][0]
        else:
            # print("m1")
            ans = D[0][0] + E[0][0] - 1
print(ans)



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

using namespace std;

using ll = long long;
using ull = unsigned long long;

int main(int argc, char const *argv[]) {
	int n;
	std::cin >> n;
	std::vector<int> v(n);
	for (size_t i = 0; i < n; i++) {
		std::cin >> v[i];
	}
	std::vector<int> vv(v);
	sort(vv.begin(), vv.end());
	int a = vv[n/2-1];
	int b = vv[n/2];

	for (size_t i = 0; i < v.size(); i++) {
		if (v[i] <= a) {
			std::cout << b << '\n';
		}
		else {
			std::cout << a << '\n';
		}
	}
	return 0;
}


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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
 
  int k;
  cin>>k;
  queue<long long>q;
  for(int i=1;i<10;i++)q.push(i);

  for(int i=0;i<k-1;i++){
         long long a=q.front(); 
         q.pop();
         if(a%10!=0)q.push(10*a+(a%10)-1);   //for every 10 digits,we can have at most 3 consecutive valid numbers ( 22,23,24- 121,122,123, 4566,4567,4565) so we leverage modulos to get always the required numbers

         q.push(10*a+a%10);   
           
         if(a%10!=9)q.push(10*a+(a%10)+1);
  }
  cout<<q.front()<<endl;

  return 0;
    
}

Measured memory_bytes: 1792
#include<stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    int i;
    int s[102];
    for (i = 0; i < n; i++)
        scanf("%d", &s[i]);
    int ans = 0;
    for (i = 0; i < n; i++)
        ans += s[i];
    int x = 0;
    if (ans % 10 == 0)
    {
        x = 200;
        for (i = 0; i < n; i++)
            if (s[i] % 10 > 0)
                if (x > s[i])
                    x = s[i];
        if (x == 200)
            x = ans;
    }
    ans -= x;
    printf("%d\n", ans);
    return 0;
}

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

typedef long long ll;

int n,q;
vector<int> g[200005];
ll inc[200005];
ll val[200005];

void dfs(int p,int x,ll pre){
    pre+=inc[x];
    val[x]=pre;
    for(int i=0;i<g[x].size();i++){
        int y=g[x][i];
        if(y!=p){
            dfs(x,y,pre);
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1;i<=q;i++){
        int x,p;
        cin>>p>>x;
        inc[p]+=x;
    }
    dfs(-1,1,0);
    for(int i=1;i<=n;i++){
        cout<<val[i]<<' ';
    }
    cout<<endl;

    return 0;
}

Measured memory_bytes: 28800
#import sys
#input = sys.stdin.readline
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np
import math


def main():
	a,b,h,m=MI()

	x=a*math.cos(2*math.pi*(h+m/60)/12)
	y=a*math.sin(2*math.pi*(h+m/60)/12)
	xx=b*math.cos(2*math.pi*m/60)
	yy=b*math.sin(2*math.pi*m/60)

	#print(x,y,xx,yy)

	xxx=x-xx
	yyy=y-yy

	#print(xxx,yyy)

	print((xxx**2+yyy**2)**0.5)
















if __name__ == "__main__":
	main()


Measured memory_bytes: 9548
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace AtCoder
{
	public class ABC
	{
		static public void Main(string[] args)
		{
			Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
			Solve();
			Console.Out.Flush();
		}

		const int mod = 1000000007;  // 10^9+7
		static int Mod(long x, int m) { return (int)((x % m + m) % m); }
		static long Mod(long x, long m) { return (x % m + m) % m; }

		static public void Solve()
		{
			//string s = Console.ReadLine();
			//int n = int.Parse(Console.ReadLine());
			//long x = long.Parse(Console.ReadLine());
			//int[] vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
			//long[] vs = Console.ReadLine().Split().Select(long.Parse).ToArray();

			string s = Console.ReadLine();
			int ans = 0;
			foreach (var c in s) {
				if (c == '+') {
					ans++;
				} else {
					ans--;
				}
			}
			Console.WriteLine(ans);

		}
	}
}


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

using namespace std;

int main() {
  long long n, k;
  cin >> n >> k;
  long long cnt = 0;
  for (int i = 1; i <= n; i++) { // b
    cnt += (n + 1) / i * min((long long)i, k) + min((n + 1) % i, k);
    if (k != 0) cnt--;
  }
  cout << n * n - cnt << '\n';
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,k,s;
    cin>>n>>k>>s;
    for(int i=0;i<k;i++)
        cout<<s<<' ';
    if(s<1000000000)
    for(int i=k;i<n;i++)
        cout<<s+1<<' ';
    else
        for(int i=k;i<n;i++)
        cout<<s-1<<' ';
}


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

#define rep(i, n) for(int i = 0; i < n; i++)

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    while(true){
        int N, Q; cin >> N >> Q;
        if(N == 0) break;
        vector<string> era_name;
        vector<int> st;
        vector<int> fin;
        rep(i, N){
            string S; int jy, wy;
            cin >> S >> jy >> wy;
            era_name.push_back(S);
            st.push_back(wy-jy+1);
            fin.push_back(wy);
        }
        rep(i, Q){
            int idx = -1;
            int year; cin >> year;
            rep(j, N){
                if(st[j] <= year && year <= fin[j]){
                    idx = j;
                    break;
                }
            }
            if(idx == -1){
                cout << "Unknown" << endl;
            }
            else{
                cout << era_name[idx] << " " << year - st[idx] + 1 << endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3136
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif


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

    int N;  cin >> N;
    vi b(N); REP(i, N) cin >> b[i];
    
    stack<int> ans;
    REP(i,N) {
        for(int i = b.size()-1; i>=0; i--) {
            if (b[i] == i + 1) {
                ans.push(b[i]);
                b.erase(b.begin() + i);
                break;
            }
        }
    }

    if (b.size()>0) {
        cout << "-1" << endl;
    } else {
        while(!ans.empty()) {
            cout << ans.top() << endl;
            ans.pop();
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define pb push_back
#define fastIO ios::sync_with_stdio(0), cin.tie(0);
#define endl '\n'
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main() {
#ifdef LOCAL
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#else
    fastIO;
#endif
    int n, k;
    cin >> n >> k;
    bool mark[10];
    memset(mark, 0, sizeof mark);
    forn(i, k) {
        int v;
        cin >> v;
        mark[v] = 1;
    }
    int aux = 0, temp = n;
    while (true) {
        // cout << temp << endl;
        bool ok = 1;
        aux = temp;
        while (aux > 0) {
            int d = aux % 10;
            aux /= 10;
            if (mark[d]) {
                ok = 0;
                break;
            }
        }
        if (ok) {
            cout << temp << endl;
            break;
        }
        temp++;
    }
    return 0;
}

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

using namespace std;
typedef long long ll;

const int N = int(1e8) + 7;

void init(){

}

void solve(){
    int a, b;
    scanf("%d %d", &a, &b);
    if(b > a) swap(a, b);
    int ans = 0;
    ans += a--;
    ans += max(a,b);
    printf("%d\n", ans);
}

const bool mtc = false;

int main(){
    int t;
    if(mtc){
        scanf("%d", &t);
        while(t--) solve();
    }
    else solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 1000000007; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


signed main() {
  int H, W;
  cin >> H >> W;

  vector<string> s(H);
  REP(i, H) cin >> s[i];

  vector<vector<int>> dp(H, vector<int>(W, 0));
  dp[0][0] = 1;

  REP(i, H) REP(j, W){
    if(s[i][j] == '#') continue;
    if(i-1 >= 0) dp[i][j] += dp[i-1][j];
    if(j-1 >= 0) dp[i][j] += dp[i][j-1];
    dp[i][j] %= MOD;
  }

  cout << dp[H-1][W-1] << endl;

  return 0;
}

Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define M1 1000000007
#define M2 998244353

#define fl(i,a,b)  for(ll i=a;i<b;i++)
#define bfl(i,a,b) for(ll i=b-1;i>=a;i--)
#define f(i,n)     for(int i=0;i<n;i++)
#define bf(i,n)    for(int i=n-1;i>=0;i--)
#define f1(i,n)    for(int i=1;i<=n;i++)
#define bf1(i,n)   for(int i=n;i>=1;i--)

#define all(v) v.begin(),v.end()
#define pll pair<long,long>
#define pii pair<int,int>



#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl

#define bn "\n"

//------------------------------------------------------------------------ 
// #define V(a) vector<a>
// #define vt() vector< tuple < int ,int ,int > > ;
// #define vector< int ,int > pv;
// vector< pair <int,int> > vect;


//------------------------------------------------------------------------

ll modI(ll a,ll m);
ll gcd(ll a,ll b);
ll powM(ll x,ll y,ll m);
ll swap(ll a,ll b);

void swap(ll& a,ll& b)
{
    ll tp=a;
    a=b;
    b=tp;
}

ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}

ll powM(ll x,ll y,ll m)
{
    ll ans=1,r=1;
    x%=m;
    while(r>0&&r<=y)
    {
        if(r&y)
        {
            ans*=x;
            ans%=m;
        }
        r<<=1;
        x*=x;
        x%=m;
    }
    return ans;
}
 
ll modI(ll a, ll m)
{
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1)
    {
        ll q=a/m;
        ll t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    }
    if(x<0) x+=m0;
    return x;
}

//---------------------------------------------------------------------------

// variable = Expression1 ? Expression2 : Expression3
// max = (n1 > n2) ? n1 : n2; 
// (n>m) ? cout<<"True"<<endl:cout<<"false"<<endl ;

// ---------------------------------------------------------------------------	

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

//----------------------------------------------------------------------------

// vector< tuple < int ,int ,int > > tv;
// vector< int ,int > pv;


//----------------------------------------------------------------------------


int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
	int tt=1;
   // cin>>tt;
	while(tt--)
	{
	    int x;
	    cin>>x;
	    if(x>=400 && x<600)
	    {
	        p1(8);
	    }
	   else if(x>=600 && x<800)
	   p1(7);
	    else if(x>=800 && x<1000)
	   p1(6);
	    else if(x>=1000 && x<1200)
	   p1(5);
	    else if(x>=1200 && x<1400)
	   p1(4);
	    else if(x>=1400 && x<1600)
	   p1(3);
	    else if(x>=1600 && x<1800)
	   p1(2);
	   else
	   p1(1);
	   
	   
	   
	    
	}
	
	return 0;
}


Measured memory_bytes: 3652
#include <stdio.h>

int main(){
  int n;

  scanf("%d", &n);

  int result = 0;

  int coins[4] = {25, 10, 5, 1};

  for(int i = 0; i < 4; i++){
    result += n/coins[i];
    n %= coins[i];
  }

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

  return 0;
}



Measured memory_bytes: 2108
from collections import namedtuple

def main():
    n,m = map(int,input().split())
    Req = namedtuple("Req","a b")
    requests = []
    for _ in range(m): #m個の要望
        a,b = map(int,input().split())
        requests.append(Req(a,b))

    requests.sort(key=lambda x:x.b)
    pre_cut = -1 #前回切断した端の左側の位置
    counter = 0 #切断の回数
    for i,req in enumerate(requests):
        if not req.a <= pre_cut < req.b:
            counter += 1
            pre_cut = req.b - 1
        else:
            continue
    print(counter)







if __name__ == '__main__':
    main()


Measured memory_bytes: 19380
#include<bits/stdc++.h>
using namespace std;
int64_t mod=1e9+7;
int main() {
  int64_t n,m,i,ans=1;
  cin>>n>>m;
  vector<int64_t> a(m+2),b(n+1);
  a.at(0)=-1;
  a.at(m+1)=n+1;
  for(i=1;i<=m;i++) cin>>a.at(i);
  b.at(0)=1;
  b.at(1)=1;
  for(i=2;i<=n;i++) b.at(i)=(b.at(i-2)+b.at(i-1))%mod;
  for(i=1;i<=m+1;i++){
    if(a.at(i)-a.at(i-1)==1){
      ans=0;
      break;
    }
    else ans=ans*b.at(a.at(i)-a.at(i-1)-2)%mod;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1792
=begin
1, 1 ~ 9 を多重ループして 一致した時点でbreakし、出力する
=end

n = gets.to_i

1.upto(9) do |i|
  1.upto(9) do |j|
    if i * j == n
      puts "Yes"
      exit
    end
  end
end

puts "No"

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

const int N=200005;
int n,m,a[N],b[N],s[N],ans;

int main()
{
	scanf("%d%d",&n,&m);
	int i,j,w,x,y;
	for(i=1;i<=n;i++)
	    scanf("%d",&a[i]),b[a[i]]++;
	for(i=1;i<=n;i++)
	    for(j=1;j<=b[i]&&j<=i;j++)
	        s[i-j+1]++;
	for(i=1;i<=n;i++)
	    if(s[i])
	        ans++;
	while(m--)
	{
		scanf("%d%d",&x,&y);
		w=a[x],a[x]=y;
		if(w-b[w]+1>=1)
		{
			s[w-b[w]+1]--;
			if(!s[w-b[w]+1])ans--;
		}
		b[w]--;
		
		b[y]++;
		if(y-b[y]+1>=1)
		{
			if(!s[y-b[y]+1])ans++;
			s[y-b[y]+1]++;
		}
		//for(i=1;i<=n;i++)cerr<<s[i]<<" ";
		printf("%d\n",n-ans);
	}
	return 0;
}


Measured memory_bytes: 3840
from functools import reduce
import math
import itertools

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M,R = (int(_) for _ in input().split())
    r = list(int(_)-1 for _ in input().split())
    a = []
    b = []
    c = []
    for i in range(M):
        s1,s2,s3 = (int(_) for _ in input().split())
        a.append(s1-1)
        b.append(s2-1)
        c.append(s3)
    d = []
    for i in range(N):
        d.append(list(INF for _ in range(N)))
        
    for i in range(N):
        for j in range(N):
            if i == j:
                d[i][j] = 0
    for i in range(M):
        if d[a[i]][b[i]] > c[i]:
            d[a[i]][b[i]] = c[i]
            d[b[i]][a[i]] = c[i]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    ans = INF
    for nodes in list(itertools.permutations(r)):
        cost = 0
        for i in range(len(nodes)-1):
            cost += d[nodes[i]][nodes[i+1]]
        ans = min(ans,cost)
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define ll      	long long int
#define PI      	acos(-1)
#define read    	freopen("in.txt","r",stdin)
#define uu      	first
#define vv      	second
#define write   	freopen("out.txt","w",stdout)
#define pii     	pair<int,int>
#define pll         pair<ll,ll>
#define INF     	1e9
#define EPS     	1e-8
#define MAX     	1000006
#define MOD     	1000000007
#define fastRead 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
int n , W , wt[200] ;
ll val[200] , dp[200][100005];


ll solve(int id ,int taken) {

     if( id == n ) return 0;
     ll &ret = dp[id][taken];
     if( ret != -1 )return ret;

     ret = solve(id+1 , taken);

     if( taken + wt[id] <= W)
        ret= max(ret , val[id] + solve(id+1 , taken+wt[id]));
     return ret;
}

int main(){
    fastRead;
    cin>>n>>W;
    for(int i =0 ; i < n ; i++ ) {
        cin>>wt[i]>>val[i];
    }
    memset(dp , -1 , sizeof dp);
    cout<<solve(0 , 0 )<<endl;
    return 0;
}


Measured memory_bytes: 156544
#include<iostream>
#include<string>
#include<algorithm>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;

int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};

int main(){
	int n,m;
	cin>>n>>m;
	cout<<(n-1)*(m-1);
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  
  int n,array[5]={0},i,a=0,b=0,c=0,j;
  
  scanf("%d",&n);
  for(i = 0;i < n ;i++ ){
    if(i == 0)  scanf("%d" ,&array[i]);
    else scanf(" %d",&array[i]);
    
    if(n == 2){
      
      if( array[0] == array[1]){
	printf("1\n");
      }
      
      
      else if( array[0] < array[1] ){
	a = array[1];
	b = array[0];
       }
      
      else if( array[0] > array[1] ){
	a = array[0];
	b = array[1];
      }
      
      for( j = 1 ; j <= b ; j++ ){
	if( a % j == 0 && b % j == 0 ){
	  
	  printf("%d\n",j);
	  
	}
      }
    }
    
    
    if(n == 3){
      if( array[0] == array[1] && array[1] == array[2] ){
	printf("1\n");
      }
      
      
      else if(array[0] < array[1] && array[1] < array[2]){
	a = array[2];
	b = array[1];
	c = array[0];
      }

      else if(array[0] < array[2] && array[2] < array[1]){
	a = array[1];
	b = array[2];
	c = array[0];
      }
      
      else if(array[1] < array[0] && array[0] < array[2]){
	a = array[2];
	b = array[0];
	c = array[1];
      }
      
      else if(array[1] < array[2] && array[2] < array[0]){
	a = array[0];
	b = array[2];
	c = array[1];
      }
      
      else if(array[2] < array[0] && array[0] < array[1]){
	a = array[1];
	b = array[0];
	c = array[2];
      }
      
      else if(array[2] < array[1] && array[1] < array[0]){
	a = array[0];
	b = array[1];
	c = array[2];
      }
      
      
      for( j = 1 ; j <= c ; j++ ){
	if( a % j == 0 && b % j == 0 && c % j == 0 ){
	  printf("%d\n",j);
	}
      }
    }
  }
  
  
  
  
  return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

// dp[i]:i文字目を先頭とした場合の，Sの部分文字列でない最短の文字列の長さ
int nex[202020][26],dp[202020],ne[26];
// ta[i]:i文字目を先頭とした場合の，遷移先(2文字目)のアルファベット(0~25=a~z)
int ta[202020];

int main(){
  string S; cin>>S;
  int N=S.length();
  rep(i,26) ne[i]=nex[N+1][i]=N+1;
  for(int i=N;i>=0;i--){
    dp[i]=202020;
    // aから貪欲に遷移先を選ぶ
    rep(j,26){
      nex[i][j]=ne[j];
      int x=dp[ne[j]];
      if(x<dp[i]){
        dp[i]=x;
        ta[i]=j;
      }
    }
    dp[i]++;
    if(i) ne[S[i-1]-'a']=i;
  }

  string ans="";
  int cur=0;
  while(cur!=N+1){
    ans+=('a'+ta[cur]);
    cur=nex[cur][ta[cur]];
  }
  cout<<ans<<endl;
  return 0;
}


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

ll dp[3001][3001];

ll dequeGame(const vector<ll>& v,int s,int e) {
    if(s>e){
        return 0;
    }

    if(dp[s][e]!=-1) {
        return dp[s][e];
    }


    ll option1 = v[s] + min(dequeGame(v,s+2,e),dequeGame(v,s+1,e-1));
    ll option2 = v[e] + min(dequeGame(v,s,e-2),dequeGame(v,s+1,e-1));

    return dp[s][e] = max(option1, option2);
}


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

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

    memset(dp,-1,sizeof dp);

    ll playerOneScore = dequeGame(v,0,n-1);
    ll playerTwoScore = accumulate(v.begin(), v.end(), (ll)0) - playerOneScore;
    cout  << playerOneScore - playerTwoScore << "\n";

    return 0;
}

Measured memory_bytes: 70784
import java.util.*;

public class Main {

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

        long x = sc.nextLong();
        long k = sc.nextLong();
        long d = sc.nextLong();

        x = Math.abs(x);

        if (Long.MAX_VALUE/k < d) {
        } else {
            if (k * d < x) {
                System.out.println(x - (k * d));
                return;
            }
        }

        if (d > x) {
                if (k % 2 == 0) {
                    System.out.println(x);
                } else {
                    System.out.println(d - x);
                }
        } else {
            long dis = x % d;
            long move = x / d;
                if ((k - move) % 2 == 0) {
                    System.out.println(dis);
                } else {
                    System.out.println(d - dis);
                }
        }

        sc.close();

        }

    }



Measured memory_bytes: 35656
#include <iostream>
#include <string>
using namespace std;
struct Dice{
    int s[6];
    void roll(char c){
        int tmp;
        if(c=='N'){
            tmp=s[0];
            s[0]=s[1];
            s[1]=s[5];
            s[5]=s[4];
            s[4]=tmp;
        }
        if(c=='E'){
            tmp=s[0];
            s[0]=s[3];
            s[3]=s[5];
            s[5]=s[2];
            s[2]=tmp;
        }
        if(c=='W'){
            tmp=s[0];
            s[0]=s[2];
            s[2]=s[5];
            s[5]=s[3];
            s[3]=tmp;
        }
        if(c=='S'){
            tmp=s[0];
            s[0]=s[4];
            s[4]=s[5];
            s[5]=s[1];
            s[1]=tmp;
        }
    }
    int top(){
        return s[0];
    }
};


int main(void){
    Dice d;
    string s;
    
    for(int i=0; i<6; i++) cin>>d.s[i];
    cin>>s;
    for(int i=0; i<s.size(); i++) d.roll(s[i]);
    cout<<d.top()<<endl;
    return 0;
}



Measured memory_bytes: 3216
//#pragma comment(linker, "/STACK:36777216")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <sstream>
#include <vector>
#include <complex>
#include <ctime>
#include <stack>

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

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector< VI > VVI;
typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define REP(i, n) for(int i = 0; i < (n); ++i)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)
#define FOR(i, x, y) for(int i = (x); i <= (y); ++i)
#define RFOR(i, y, x) for(int i = (x); i >= (y); --i)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort(ALL(a)) 
#define CLEAR(x) memset(x, 0, sizeof x);
#define COPY(FROM, TO) memcpy(TO, FROM, sizeof TO);
#define UNIQUE(c) SORT(c),(c).resize(unique(ALL(c))-(c).begin())
#define pb push_back
#define mk make_pair
#define sqr(x) ((x)*(x))
#define X first
#define Y second
//typedef tree<int, null_type, less<int>, 
//  rb_tree_tag, tree_order_statistics_node_update> order_set;

const long double PI = acos(-1.0);
const double EPS = 1E-6;
const int INF = 2 * (1e+9) + 1;
const int MAXN = 3 * 100000001;
const int MOD = (1e+9) + 7;


int n, m, x;
int c[12];
int a[12][12];

int main() {
    cin >> n >> m >> x;
    REP(i, n) {
        cin >> c[i];
        REP(j, m) {
            cin >> a[i][j];
        }
    }
    int price = INF;
    REP(mask, (1 << n)) {
        int cur_price = 0;
        VI cur_lvl(m, 0);
        REP(i, 12) {
            if (mask & (1 << i)) {
                cur_price += c[i];
                REP(j, m) {
                    cur_lvl[j] += a[i][j];
                }
            }
        }
        int u = 1;
        REP(i, m) {
            if(cur_lvl[i] < x) {
                u = 0;
            }
        }
        if (u) {
            price = min(price, cur_price);
        }
    }
    if (price == INF) {
        cout << -1;
    } else cout << price;
    return 0;
}

Measured memory_bytes: 3156
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    int n, m, k;
    bool a = false;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        int sum = 0;
        for(int j = 1; j <= m; j++){
            sum = (n - i) * j + (m - j)* i;
            if(sum == k)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << (k == n * m ? "Yes":"No") << endl;
}

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

int main()
{
    int n,i,s=0;
    cin>>n;
    n*=2;
    int a[n];
    
    for(i=0;i<n;i++)
    cin>>a[i];
    
    sort(a,a+n);
    for(i=0;i<n;i+=2)
    s+=a[i];
    
    cout<<s;
    return 0;
}

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

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int x = (c + b - 1) / b;
    int y = (a + d - 1) / d;
    if (x <= y) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3580
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import bisect
import numpy as np
import math
from collections import deque
from collections import defaultdict
from math import gcd

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())

if N == 1:
    print(0)
else:
    fact = factorization(N)

    ans = 0
    for p, r in fact:
        index = 0
        cum_sum = 1
        cnt = 1
        while cum_sum <= r:
            index += 1
            cum_sum += cnt + 1
            cnt += 1

        ans += index
    print(ans)

Measured memory_bytes: 27172
#include <bits/stdc++.h>
using namespace std;
int main()
{
    map<string,int>m;
    map<string,int>::iterator it;
    int n,mm;
    cin >>n;
    for(int i=0;i<n;i++){
        string s;
        cin >>s;
        m[s]++;
    }
    cin >>mm;
    for(int i=0;i<mm;i++){
        string s;
        cin >>s;
        m[s]--;
        if(m[s]<0){m[s]=0;}
    }
    int ans=INT_MIN;
    for(it = m.begin();it!=m.end();it++){
        ans=max(ans,it->second);
    }
    cout <<ans<<endl;
}


Measured memory_bytes: 256
/*
		@Author :- Gaurav Bharti
		National Institute of Technology, Jamshedpur.
*/
 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define empb emplace_back
#define mp make_pair
#define F first
#define S second
#define endl "\n"
#define vii vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vpii vector<pii>
#define mapii map<int,int> 
#define mapll map<ll,ll>
#define all(a) a.begin(),a.end()
#define test ll t; cin>>t; while(t--)
#define prec(n) fixed<<setprecision(n)
#define jaldibazi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007

char mat[8][8];

int solve(){
	int ans=0;

	int h, w, k; cin>> h >> w >>k;
	for(int i = 0; i < h; ++i){
		for( int j=0; j< w; ++j) cin >> mat[i][j];
	}

	for(int maskr=0; maskr < (1<<h) ; ++maskr){
		for(int maskc = 0; maskc < (1<< w);++maskc){
			int cb=0;

			for(int i=0; i<h; ++i){
				for(int j=0;j< w; ++j){
					if(((maskr>>i) & 1 )== 0  and ((maskc >>j)& 1 )==0 and mat[i][j]=='#'){
						cb+=1;
					}
				}
			}
			if(cb==k) ans+=1;
		}
	}
	return ans;
} 
 
int main(){
	jaldibazi;
 
	cout << solve() << endl;
}

Measured memory_bytes: 3564
import heapq
import sys
N,M=map(int,input().split())
A=sorted(list(map(int,input().split())))
lst=[[0,0] for _ in range(M)]
h=[]
for i in range(M):
  lst[i]=list(map(int,input().split()))
  heapq.heappush(h,[-1*lst[i][1],lst[i][0]])
i=0
while len(h)!=0:
    v=heapq.heappop(h)
    v1,v2=-1*v[0],v[1]
    while i<=N-1 and A[i]<v1 and v2!=0:
        A[i]=v1
        i+=1
        v2-=1
    if v2>=1:
        print(sum(A))
        sys.exit()
print(sum(A))

Measured memory_bytes: 44872
N = int(input().rstrip())
K = int(input().rstrip())

xs = list(map(int, input().rstrip().split()))

total = 0

for i in range(len(xs)):
    bx = xs[i]
    by = i + 1
    v1 = bx * 2
    v2 = abs(K - bx) * 2
    v = v1 if (v1 < v2) else v2 
    total += v
    
print(total)


Measured memory_bytes: 3060
N=int(input())
K=int(input())
s=str(N)
N=len(s)

# dp[i][smaller][k] :=i桁目までで0以外の数を使用したのがk個である数の個数。
# smallerが1ならNより小さく、0ならNと等しい数であるとする。
dp=[[[0]*(K+2) for j in range(2)] for i in range(N+1)]
dp[0][0][0]=1
for i in range(N):
  for k in range(K+1):
    ni=int(s[i])
    # i桁目まででNより小さいならi+1桁目は何でも良い
    dp[i+1][1][k+1]+=dp[i][1][k]*9 # i+1桁目が0以外
    dp[i+1][1][k]+=dp[i][1][k]     # i+1桁目が0
    # i桁目まででNと同じで、i+1桁目はNより小さい時
    if ni>0:
      dp[i+1][1][k+1]+=dp[i][0][k]*(ni-1) # i+1桁目が0以外
      dp[i+1][1][k]+=dp[i][0][k]          # i+1桁目が0以外
    # i桁目までNと同じで、i+1桁目もNと同じ数の時
    if ni>0:
      dp[i+1][0][k+1]=dp[i][0][k] # i+1桁目が0以外
    else:
      dp[i+1][0][k]=dp[i][0][k]   # i+1桁目が0
print(dp[N][0][K]+dp[N][1][K])


Measured memory_bytes: 3064
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

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

    vector<ll> balls;
    vector<ll> flags(n, 0);
    for(ll i = n - 1; i >= 0; --i){
        const ll j = i + 1;
        ll tmp = 0;
        for(ll k = 2 * j; k <= n; k += j){
            tmp += flags.at(k - 1);
        }
        if(tmp % 2 == as.at(i)){
            flags.at(i) = 0;
        }else{
            balls.push_back(i);
            flags.at(i) = 1;
        }
    }
    cout << balls.size() << endl;
    for(ll i = 0; i < balls.size(); ++i){
        cout << (balls.at(i) + 1);
        if(i == balls.size() - 1){
            cout << endl;
        }else{
            cout << ' ';
        }
    }
    return 0;
}


Measured memory_bytes: 4980
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    int h,w;
    cin>>h>>w;
    string C[100];
    rep(i,h) cin>>C[i];
    int dp[101][101];
    rep(i,h)rep(j,w) dp[i][j]=1e9;
    if(C[0][0]=='#') dp[0][0]=1;
    else dp[0][0]=0;
    rep(i,h)rep(j,w){
        if(i>0) dp[i][j]=min(dp[i][j],dp[i-1][j]+(C[i-1][j]!=C[i][j]));
        if(j>0) dp[i][j]=min(dp[i][j],dp[i][j-1]+(C[i][j-1]!=C[i][j]));
    }
    cout<<(dp[h-1][w-1]+1)/2<<"\n";
}

Measured memory_bytes: 256