akhauriyash/Code-Regression huggingface dataset:
fun main(args: Array<String>) {
    val (n, k) = readIntList()
    val a = readIntList()

    var num = MutableList(n + 1) { 0 }

    a.forEach { num[it]++ }
    num.removeAll { it == 0 }
    val sorted = num.sorted().reversed()
    var tmp = a.toSet().size - k
    val ans = if (tmp > 0) {
        sorted.takeLast(tmp).sum()
    } else {
        0
    }
    println(ans)
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)

Measured memory_bytes: 75816
S = input()
max_pos = len(S) - 1

ans = 0
if max_pos > 0:
    for i in range(1 << max_pos):
        total = 0
        fragment = ""
        for j in range(len(S)):
            digit = S[j]
            fragment += digit
            if j == len(S) - 1 or ((i >> j) & 1) == 1:
                total += int(fragment)
                fragment = ""
        ans += total
else:
    ans = int(S)

print(ans)

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


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

    string s;
    cin>>s;
    int n=s.size();
    for(int i=0;i<n-1;i++){
        if(s[i]==s[i+1]){
            cout << i+1 << " " << i+2<<endl;
            return 0;
        }
    }
    for(int i=0;i<n-2;i++){
        int cnt[26]={};
        for(int j=0;j<3;j++){
            cnt[s[i+j]-'a']++;
            if(cnt[s[i+j]-'a']==2){
                cout << i+1 << " " << i+3 << endl;
                return 0;
            }
        }
    }
    cout << -1 << " " << -1 << endl;
    return 0;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    // sort(a.begin(), a.end());
    map<int, int> m;
    for (int i = 0; i < n; ++i) {
        m[a[i]]++;
    }
    int eaten = 0;
    int twoes = 0;
    for (auto p : m) {
        if (p.second == 2) {
            twoes++;
        } else if (p.second >= 3 && p.second % 2 == 1) {
            eaten += p.second - 1;
        } else if (p.second >= 3 && p.second % 2 == 0) {
            eaten += p.second - 2;
            twoes++;
        }
    }
    eaten += 2 * ((twoes + 1) / 2);
    cout << n - eaten << "\n";
    return 0;
}

Measured memory_bytes: 5376
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int n = sc.nextInt();
        String ch;
        int t,f;


        for(int i=0;i<n;i++){
            String test = sc.next();

            if(test.equals("replace")){
            	t=sc.nextInt();
            	f=sc.nextInt();
            	ch=sc.next();
            	str = replace(str,t,f+1,ch);
            }
            else if(test.equals("reverse")){
            	t=sc.nextInt();
            	f=sc.nextInt();
            	char rev[]= str.substring(t,f+1).toCharArray();
            	char rev2[] = new char[rev.length];
            	for(int j=0;j<rev.length;j++){
            		rev2[j]=rev[rev.length-1-j];
            	}
            	str=str.replaceFirst(str.substring(t,f+1),String.valueOf(rev2));


            }else if(test.equals("print")){
            	t=sc.nextInt();
            	f=sc.nextInt();
            	System.out.println(str.substring(t,f+1));

            }else{
            	System.out.println("EEE");
            }



        }
        sc.close();
    }
    
    static String replace(String str,int a,int b, String ch) {
    	char rep[]=str.toCharArray(),c[]=ch.toCharArray();
    	for(int i=a;i<b;i++)rep[i]=c[i-a];
    	return String.valueOf(rep);
    }
}


Measured memory_bytes: 30300
import sys
input = sys.stdin.readline
N, K = [int(x) for x in input().strip().split()]
A = [int(x) for x in input().strip().split()]
T_A = 0
T_A_all = 0
for i,a in enumerate(A):
    T_A += len([1 for x in A[i+1:] if a > x])
    T_A_all += len([1 for x in A if a > x])
a = T_A
z = T_A + T_A_all * (K -1)
print(int((K*(a+z)//2)%((10**9)+7)))


Measured memory_bytes: 3188
h,w,k=map(int, input().split()) 
s=[list(map(str,list(input().split()))) for i in range(h)]

ans = 0
bk = 0
pt1 = []
pt2 = []

for i in range(2 ** h):
    tmp1 = [False] * (h)
    for j in range(h):
        if i >> j & 1:
            tmp1[j] = True
    pt1.append(tmp1)

for i in range(2 ** w):
    tmp2 = [False] * (w)
    for j in range(w):
        if i >> j & 1:
            tmp2[j] = True
    pt2.append(tmp2)

for i in range(len(pt1)):
    for j in range(len(pt2)):
        for x in range(h):
            if (pt1[i][x]==True):
                bk = bk + s[x][0].count('#')
        
        for y in range(w):
            if (pt2[j][y]==True):
                for z in range(h):
                    if (pt1[i][z]==True and s[z][0][y]=='#'):
                        bk == bk
            else:
                for z in range(h):
                    if (pt1[i][z]==True and s[z][0][y]=='#'):
                        bk -= 1

        if bk == k:
            ans += 1
        #print(pt1[i],pt2[j],bk)
        bk = 0

print(ans)


Measured memory_bytes: 8980
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
ans = 0
for _ in range(n):
    a = list(map(int, input().split()))
    total = 0
    for i in range(m):
        total += a[i] * b[i]
    total += c
    if total > 0:
        ans += 1
print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#define int long long
#define ll getchar();getchar();return 0;
using namespace std;
int a[114];
signed main(){
	int n, x,cnt=0;
	cin >> n >> x;
	for (int i = 0; i < n; i++)cin >> a[i];
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		cnt += a[i];
	}
	cout << (x - cnt) / a[0] + n << endl;
	ll
}

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

typedef long long int lli;
#define pb push_back
#define gcd __gcd
#define MOD 1000000007
#define mod2 998244353
#define PI 3.141592653589793238462643383279
#define forz(i,n) for(long long int i=0;i<n;i++)

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1,u,j;
    //cin>>t;
    for(u=1;u<=t;u++){
        //cout<<sin()
        lli n,i,j,a,b,c,d,k,n1,n2,n3,current,h,m;
        cin>>n>>m;
        vector<lli> adj[n+1];
        for(i=0;i<m;i++){
            cin>>a>>b;
            adj[a].pb(b);
            adj[b].pb(a);
        }
        vector<lli> visit(n+1,0);
        vector<lli> bap(n+1,0);
        queue<lli> Q;
        Q.push(1);
        visit[1]=1;
        while(!Q.empty()){
            int t=Q.front();
            Q.pop();
            for(i=0;i<adj[t].size();i++){
                if(visit[adj[t][i]]==0){
                    Q.push(adj[t][i]);
                    visit[adj[t][i]]=1;
                    bap[adj[t][i]]=t;
                }
            }
        }
        for(i=2;i<=n;i++){
            if(visit[i]==0){
                cout<<"No"<<endl;
                return 0;
            }
        }
        cout<<"Yes"<<endl;
        for(i=2;i<=n;i++) cout<<bap[i]<<endl;
    }
}

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


const long mod=1000000007;

using namespace std;
int main(){
  long n;
   cin >>n;
  
  vector<long> a(n),b(n);

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

  for(int i=0;i<n;i++) b[i]=max(n-1-2*i,long(0))+max(long(0),2*i-n+1);
  
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  
  for(int i=0;i<n;i++){
   if(a[i]!=b[i]) {
     cout << 0 << endl;
     return 0;
   }
   }
  
  long res=1;
  for(int i=0;i<n/2;i++) {
    res*=2;
    res%=mod;
  }
    
  cout << res << endl;
    
  
}

Measured memory_bytes: 1792
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int N, M;
    scan(N, M);

    auto adj = new int[][](N, 0);
    foreach (i ; 0 .. M) {
        int xi, yi;
        scan(xi, yi);
        xi--, yi--;
        adj[yi] ~= xi;
    }

    auto dp = new int[](N);
    dp[] = -1;

    int rec(int v) {
        if (dp[v] != -1) {
            return dp[v];
        }
        dp[v] = 0;

        foreach (u ; adj[v]) {
            chmax(dp[v], rec(u) + 1);
        }

        return dp[v];
    }

    int ans;

    foreach (i ; 0 .. N) {
        chmax(ans, rec(i));
    }

    writeln(ans);
}



void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

bool f[1000001];
ll N;
ll A[200001];
vector<ll> v;
ll t[1000001];

int main(){
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> A[i];
        v.push_back(A[i]);
        t[A[i]]++;
    }
    sort(v.begin(),v.end());
    for(int i=0;i<N;i++){
        if(f[v[i]]) continue;
        if(i > 0){
            if(v[i] == v[i-1]) continue;
        }
        for(int j=2;j*v[i]<=1000000;j++) f[j*v[i]] = true;
    }
    ll c = 0;
    for(int i=0;i<N;i++){
        if(f[A[i]]) continue;
        if(t[A[i]]>1) continue;
        c++;
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 15168
//#pragma GCC optimize("-Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//order_of_key(x) : number of items less than x
//find_by_order(x) : iterator to x

#define mem(dp,a)           memset(dp,a,sizeof dp)
#define rep(i,a,b)          for(ll i=a;i<b;i++)
#define pb(x)               push_back(x)
#define mp(x,y)             make_pair(x,y)
#define fastio              ios_base::sync_with_stdio(false);cin.tie(NULL)
#define F                   first
#define S                   second
#define all(v)              (v).begin(),(v).end()

const ld pi=3.14159265359;
ll INF=1e18+10;
ll MOD=998244353;
ll mod=1e9+7;

inline ll add(ll a,ll b,ll m){
    if((a+b)>=m)return (a+b)%m;
    return a+b;
}

inline ll mul(ll a,ll b,ll m){
    if((a*b)<m)return a*b;
    return (a*b)%m;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n,m;cin>>n>>m;
    ll sum=0;
    ll a[m];rep(i,0,m)cin>>a[i],sum+=a[i];
    if(n-sum<0)cout<<-1;
    else cout<<(n-sum);
}


Measured memory_bytes: 3716
// Created by arvybhatt

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define p_b push_back
#define m_p make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)

using namespace std;
using ll = long long;

bool comp(pair<int,int> a,pair<int,int> b)
{
	return a.F<b.F;
}

int main()
{
    fast;
    
    ll n;cin>>n;
    ll w;cin>>w;
    vector<pair<ll,ll> > v;	
    for(int i=0; i<n; i++)
    {
    	ll x,y;cin>>x>>y;
    	v.p_b({x,y});
    }
    sort(v.begin(),v.end(),comp);

    ll dp[n+1][w+1];
    for(int i=0; i<=w; i++)
    	dp[0][i]=0;
    for(int i=0; i<n; i++)
    	dp[i][0]=0;
    for(int i=1; i<=n; i++)
    {
    	for(int j=1; j<=w; j++)
    	{
    		if(j>=v[i-1].F)
    		{
    			//cout<<"y"<<"\n";
    			dp[i][j]=max(dp[i-1][j],(v[i-1].S + dp[i-1][j-v[i-1].F] ) );
    			//cout<<v[i-1].S<<" "<<dp[i-1][j-v[i-1].F]<<" "<<(v[i-1].S + dp[i-1][j-v[i-1].F] )<<"\n";
    		}
    		else
    		{
    			dp[i][j]=dp[i-1][j];
    		}
    		
    	//cout<<dp[i][j]<<" ";
    	}
    	//cout<<"\n";
    }


    cout<<dp[n][w];



    return 0;
}


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

int main()
{
    string nums;
    while(cin >> nums)
    {
        vint pir(10);
        
        rep(i, 10)
            pir[i] = nums[i] - '0';
        
        while(pir.size() != 1)
        {
            vint n(pir.size()-1);
            rep(i, pir.size()-1)
                n[i] = (pir[i] + pir[i + 1]) % 10;
            pir = n;
        }
        
        cout << pir[0] << endl;
    }
}

Measured memory_bytes: 0
//
//  main.cpp
//  CoderProj
//
//  Created by Minoru Hayashi on 2020/03/12.
//  Copyright © 2020 Minoru Hayashi. All rights reserved.
//
//
//  
//

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

#define REP(i,n) for (int i=0; i<(n); i++)
#define REP2(i,x,n) for (int i=x; i<(n); i++)
#define ALL(n) begin(n), end(n)

using ll = long long;

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

// const ll INF = 1LL<<60;
// const int INF = 1<<29;
 const ll MOD = 1000000007;

//#define __DBG__




void solve(void){
  
  int N;
  
  cin >> N;
    
  vector<ll> A(N);
  
  ll ans=0;
  
  REP(i,N){
    cin >> A[i];
//    cout << bitset<60>(A[i]) << endl;
  }
  
  REP(j,60){
    ll n0=0;
    ll n1=0;
    REP(i,N){
      if((A[i]>>j)&1LL){n1++;}else{n0++;}
    }
    ll y=(1LL<<j)%MOD;
    ll tmp=(n1*n0)%MOD;
    ans += (tmp*y)%MOD;
    ans = ans%MOD;
//    cout << j << ":" << n0 << " " << n1 << endl;
  }
  
  
  cout << ans << endl;

  return;
   
}


int main(int argc, const char * argv[]) {


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

    solve();
 
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
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; }

const long long INF = 1LL << 60;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // DP テーブル
    long long dp[100010];

    // 入力
    int a;
    while(cin>>a, a){  
        // 初期化 
        long long dp[100010];
        rep(i,100010) {
            dp[i] = INF;
        }

        // 初期条件
        dp[0] = 1;   

        // ループ
        rep2(i,a+1) {
            if (i > 2) {
                if(dp[i] !=  0) {
                    dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
                }
            }
            else if (i > 1){
                if(dp[i] !=  0) dp[i] = dp[i-1] + dp[i-2];
            }
            else {
                dp[i] = dp[i-1];
            }
        } 
        cout << ((dp[a] + 9)/10 + 364)/365 << endl;
    }
    return 0;
}


Measured memory_bytes: 3908
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

struct Graph {
    static constexpr ll INF = 1LL << 60;
    struct Vertex { ll c; };
    struct Edge { int i, c; };
    Graph(int n) : v(n, { -INF }), e(n), n(n) {}
    void add_edge(int i, int j, int c) {
        e[i].push_back({ j, c });
    }
    ll bellman_ford(int i0, int i1) {
        v[i0].c = 0;
        for (int k = 0; k < n * 2 - 1; k++) {
            for (int i = 0; i < n; i++) {
                if (v[i].c == -INF) continue;
                for (auto o : e[i]) {
                    ll c = v[i].c + o.c;
                    if (c > v[o.i].c) {
                        v[o.i].c = k < n - 1 ? c : INF;
                    }
                }
            }
        }
        return v[i1].c;
    }
    vector<vector<Edge>> e;
    vector<Vertex> v;
    int n;
};

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

    int n, m, p;
    cin >> n >> m >> p;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        g.add_edge(a, b, c - p);
    }

    ll r = g.bellman_ford(0, n - 1);
    cout << (r == g.INF ? -1 : max(r, 0LL)) << endl;

    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define MAXN maxn

using namespace std;

int N;
int cnt;

signed main()
{
	IO;
	cin >> N;

	for (int c = 1; c < N; c++) {
		int t = N - c;
		for (int b = 1; b * b <= t; b++) {
			if (!(t % b)) {
				cnt += 2;
				if (b * b == t) {
					cnt--;
				}
			}
		}
	}

	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3648
n,k=map(int,input().split())
l=list(map(int,input().split()))
tl=[-1]*n
tl[0]=0
index=0
i=1
while True:
  index=l[index]-1
  if k==i:
    break
  elif tl[index]==-1:
    tl[index]=i
  else:
    last=(k-tl[index])%(i-tl[index])
    for i in range(last):
      index=l[index]-1
    break
  i=i+1
print(index+1)

Measured memory_bytes: 32368
a = int(input(''))
b = int(input(''))
c = int(input(''))
d = int(input(''))
e = int(input(''))
list_i = [a,b,c,d,e]
 
min_n = list_i[0] % 10
v = 0
count = 0
 
for i in range(len(list_i)):
 if list_i[i] % 10 < min_n and list_i[i] % 10 != 0:
  count = i
 
for i in range(len(list_i)):
 if i == count or list_i[i] % 10 == 0:
  v = v + list_i[i]
 else:
  v = v + list_i[i] + ( 10 - list_i[i] % 10)
 
print v

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

int main(void){
  int N;
  cin >> N;
  int flag = 0;
  for(int i = 1; i < 10; i++){
   if(N % i == 0 && N / i < 10){
     cout << "Yes";
     flag = 1;
     break;
   }
  }
  if(flag == 0) cout << "No";
 return 0; 
}

Measured memory_bytes: 256
import scala.io.Source

object Main{
  def main(args: Array[String]){
    var list = List[String]()
    for(in <- Source.stdin.getLines.toList){
      list = in :: list
    }

    for(i <- 0 until list.length){
      //if(list(list.length - i - 1).size > 2){
        val arr = list(list.length - i - 1).split(Array(' '))

        if(!(arr(0).toInt == 0 && arr(1).toInt == 0)){
          for(i <- 0 until arr(0).toInt){
            for(j <- 0 until arr(1).toInt){
              print("#")
            }
            println
          }
          println
        }
      //}
    }
  }
}

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

long long knapsack(int W, vector<int> &weights, vector<int> &values, int n) {
    vector<vector<long long> > dp(n+1, vector<long long>(W+1, 0));
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=W; j++) {
            if(j >= weights[i-1]) {
                dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][W];
}

int main() {
    int n, w;
    cin>>n>>w;
    vector<int> weights(n), values(n);
    for(int i = 0; i<n; i++) {
        cin>>weights[i]>>values[i];
    }
    cout<<knapsack(w, weights, values, n)<<"\n";
}


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

int main(){
  int N;
  string S;
  int count[26] = {};
  
  cin >> N;
  cin >> S;
  
  for(int i=0; i<N; i++){
    count[S[i] - 'a']++;
  }
  
  long long int ans = 1;
  for(int i=0; i<26; i++){
    ans *= count[i] + 1;
    ans %= 1000000007;
  }
  cout << ans-1 << endl;
  return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
using namespace std;

#define MAX 300002
int sumA[MAX], sumB[MAX];

int main(){
  int n;
  string s;

  while (cin >> n >> s) {
    fill(sumA, sumA + MAX, 0);
    fill(sumB, sumB + MAX, 0);
    
    for (int i = 0; i < n; i++) {
      if (s[i] == 'W') {
        sumA[i + 1] = 1;
      }
      sumA[i + 1] += sumA[i];
    }

    for (int i = n - 1; i >= 0; i--) {
      if (s[i] == 'E' && i > 0) {
        sumB[i - 1] = 1;
      }
      sumB[i - 1] += sumB[i];
    }

    int ans = INT_MAX;

    for (int i = 0; i < n; i++) {
      ans = min(ans, sumA[i] + sumB[i]);
    }

    cout << ans << endl;
  }
}


Measured memory_bytes: 3076
#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=((int)(n)); i>0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>=0; --i)
# define ALL(v) v.begin(), v.end()
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<typename T> void dump(T e){std::cout << e << std::endl;}
template<typename T> void dump(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void dump(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ dump(v); } }
template <typename T>
void dump_stack(std::stack<T>& stack) {
  std::stack<T> temp;
  while (!stack.empty()) {
    T top = stack.top(); stack.pop();
    std::cout << top << " ";
    temp.push(top);
  }
  std::cout << endl;
  while (!temp.empty()) {
    T top = temp.top(); temp.pop();
    stack.push(top);
  }
}
template <typename T>
void dump_queue(std::queue<T>& queue) {
  std::queue<T> temp;
  while (!queue.empty()) {
    T top = queue.front(); queue.pop();
    std::cout << top << " ";
    temp.push(top);
  }
  std::cout << endl;
  while (!temp.empty()) {
    T top = temp.front(); temp.pop();
    queue.push(top);
  }
}

typedef long long ll;

struct PAIR{
public:
  string name;
  int q;
};


int main(){
  int n,time; cin >> n >> time;
  queue<PAIR> q;
  string s;
  int qt;
  rep (i,n) {
    cin >> s >> qt;
    q.push(PAIR{s,qt});
  }
  int cnt_time=0;
  while(!q.empty()){
    PAIR d = q.front(); q.pop();
    if (d.q > time) {
      cnt_time += time;
      q.push(PAIR{d.name,d.q-time});
    } else {
      cnt_time += d.q;
      cout << d.name << " " << cnt_time << endl;
    }
  }
}



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

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && a == c) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
}

Measured memory_bytes: 256
N,M,X=map(int,input().split())
C = [0] * N
A = [ [0 for i in range(M)] for i in range(N) ]
for i in range(N):
  CA = list(map(int,input().split()))
  C[i] = CA[0]
  A[i] = CA[1:]
INF = 100000000
ans = INF
for i in range( 1 << N ):
  cost = 0
  r = [0] * M
  for j in range(N):
    if (i & (1 << j) != 0):
      cost += C[j]
      for k in range(M):
        r[k] += A[j][k]
  ok = 1
  for k in range(M):
    if r[k] < X:
      ok = 0
  if ok == 1:
    ans = min(ans, cost)
#  print(" ",i," ",ok)
#  print(" ",r)
if ans == INF:
  print("-1")
else:
  print(ans)


Measured memory_bytes: 9248
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <sstream>
#include <algorithm>

using namespace std;
vector<vector<int> > senbei;
int H, W;


int main() {
	while (1) {
		cin >> H >> W;
		if (H + W == 0) break;
		senbei.resize(H);
		vector<int> b;
		b.resize(H);
		for (int i = 0; i < H; i++) {
			senbei[i].resize(W);
			b[i] = 0;
		}
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				cin >> senbei[i][j];
			}
		}
		int H2 = pow(2, H);
		int max = -1;
		
		for (int i = 0; i < H2; i++) {
			if (i != 0) {
				for (int j = 0; j < b.size(); j++) {
					if (b[j] == 0) {
						b[j] = 1;
						break;
					}
					else {
						b[j] = 0;
					}
				}
			}
			int count = 0;

			for (int k = 0; k < W; k++) {
				int omote = 0, ura = 0;
				for (int j = 0; j < H; j++) {
					if (b[j] == senbei[j][k]) omote++;
				}
				count += omote > H-omote ? omote : H-omote;
			}
			if (max < count) max = count;
		}
		cout << max << endl;
	}
	return 0;
}

Measured memory_bytes: 3528
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
  ll N,c;
  cin >> N;
  vector<ll> vec(N);
  for (ll i = 0; i < N; ++i) cin >> vec[i];
  const vector<ll> convec(vec);
  sort(vec.begin(),vec.end());
  ll diff = 0;
  for (ll i = 0; i < N; ++i) if (convec[i] != vec[i]) diff++;
  if (diff <= 2) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


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

int main() {
  std::string S;
  std::cin >> S;
  std::vector<bool> flags(27, true);
  for (size_t i = 0; i < S.size(); i++) flags[S[i] - 'a'] = false;

  uint32_t i = 0;
  while (!flags[i]) i++;

  if (i == (flags.size() - 1))
    std::cout << "None" << std::endl;
  else
    std::cout << static_cast<char>('a' + i) << std::endl;

  return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<iomanip>
#include<vector>
using namespace std;
using ll=long long;


int main(){
	const int M=100000;
	int n,a[M],tmp;

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

	sort(a,a+n);
	tmp=a[0];
	for(int i=0;i<n;i++){
		if(tmp%a[i]==0)continue;
		if(tmp>a[i]%tmp&&a[i]%tmp!=0){
			tmp=a[i]%tmp;
			i=-1;
		}
	}
	cout<<tmp<<endl;
}

Measured memory_bytes: 640
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			long H = Integer.parseInt(sc.next());
			long W = Integer.parseInt(sc.next());
			if(H==1||W==1) {
				System.out.println(1);
			}else {				
				System.out.println((H*W+1)/2);
			}
		}	
	}
}

Measured memory_bytes: 35504
h,w = gets.split.map(&:to_i)

a = []
h.times{a << gets.chomp.split("")}

(h-1).downto(0) do |i|
    a.delete_at(i) if a[i].all?{|e| e == "."}
end

(w-1).downto(0) do |i|
    a.each{|e| e.delete_at(i)} if a.all?{|e| e[i] == "."}
end

puts a.map{|e| e.join}

Measured memory_bytes: 2556
#pragma region _head

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<iomanip>
#include<queue>
#include<stack>
#include<numeric>
#include<utility>
#include<regex>

void Init() {
	std::cin.tie(0); std::ios::sync_with_stdio(false);
	struct Init_caller { Init_caller() { Init(); } }caller;
}

#pragma region _define

#define int LL
#define f(i,a,b) for(LL i=a;i<b;i++)
#define f_vI(v,n) f(i,0,n)cin>>v[i]
#define f_v2I(v1,v2,n) f(i,0,n)cin>>v1[i]>>v2[i]
#define f_v3I(v1,v2,v3,n) f(i,0,n)cin>>v1[i]>>v2[i]>>v3[i]
#define f_vO(v,n) f(i,0,n)cout<<v[i]<<endl
#define ei else if
#define all(a) a.begin(),a.end()
#define size(s) ((LL)s.size())
#define F first
#define S second
#define check() cout<<"! ! !"
#define endl "\n"
#define _y() cout<<"Yes"<<endl
#define _Y() cout<<"YES"<<endl
#define _n() cout<<"No"<<endl
#define _N() cout<<"NO"<<endl
#define INT_INF 1<<29
#define LL_INF 1LL<<60
#define MOD 1000000007

#pragma endregion

#pragma region _using

using namespace std;

using LL = long long;
using st = string;
using vi = vector<LL>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<st>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using qi = queue<LL>;
using qc = queue<char>;
using qs = queue<st>;
using si = stack<LL>;
using sc = stack<char>;
using ss = stack<st>;
using pi = pair<LL, LL>;
using ppi = pair<pi, LL>;
using mll = map<LL, LL>;
using mcl = map<char, LL>;
using vpi = vector<pi>;
using vppi = vector<ppi>;

#pragma endregion

struct edge {
	int from, to, cost;
};

void y_n(bool p) {
	p ? _y() : _n();
}

void Y_N(bool p) {
	p ? _Y() : _N();
}

LL vmax(vi v, LL n) {
	int MAX = 0;
	f(i, 0, n) {
		MAX = max(MAX, v[i]);
	}
	return MAX;
}

LL vmin(vi v, LL n) {
	int MIN = LL_INF;
	f(i, 0, n) {
		MIN = min(MIN, v[i]);
	}
	return MIN;
}

LL gcd(LL a, LL b) {
	LL r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}
LL lcm(LL a, LL b) {
	return (a / gcd(a, b) * b);
}

//素数判定
bool is_prime(int n) {
	for (int i = 2; i*i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

//エラトステネスの篩
void sieve(LL n) {
	vb s(n + 1, true);
	f(i, 2, n + 1) {
		for (int j = 2; i*j <= n; j++) {
			s[i*j] = false;
		}
	}
	cout << "2から" << n << "までの素数" << endl;
	f(i, 2, n + 1) {
		if (s[i]) {
			cout << i << " ";
		}
	}
}

//階乗計算
LL factorial(LL n) {
	LL a = 1, ret = 1;
	while (a < n) {
		a++;
		ret *= a;
		ret %= MOD;
	}
	return ret;
}


#pragma endregion 


/*****************************************************************************/
signed main(void) {
	int a, b;
	cin >> a >> b;
	if (a > 8 || b > 8) {
		cout << ":(";
	}
	else {
		cout << "Yay!";
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main(){
  int N, tmp;
  map<int, pair<int, int>> card;
  vector<vector<bool>> flags;
  for (int i=0; i<3; i++){
    for (int j=0; j<3; j++){
      cin >> tmp;
      card[tmp] = pair<int, int>(i, j);
    } 
    flags.emplace_back(vector<bool>(3, false));
  }
  
  cin >> N;
  for (int i=0; i<N; i++){
    cin >> tmp;
    if (card.find(tmp) != card.end()){
      pair<int, int> p = card[tmp];
      flags[p.first][p.second] = true;
    }
  }
  bool ans = false;
  for (int i=0; i<3; i++){
    for (int j=0; j<3; j++){
      cerr << flags[i][j] << " ";
    }
    cerr << endl;
  }
  for (int i=0; i<3; i++){
    bool flag_v = true;
    bool flag_h = true;
    for (int j=0; j<3; j++){
      flag_v &= flags[j][i];
      flag_h &= flags[i][j];
    }
    ans |= (flag_v | flag_h);
    if (ans) break;
  }
  if (!ans){
    ans |= (flags[0][0] & flags[1][1] & flags[2][2]);
    ans |= (flags[0][2] & flags[1][1] & flags[2][0]);
  }
  cout << (ans ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
#![allow(unused)]

use std::{cell, cmp, collections, convert, fmt, io, iter, ops, str};

use cell::{Cell, RefCell};
use cmp::Ordering::{Equal, Greater, Less};
use collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
use io::{Read, Write};

#[cfg(feature = "debug")]
macro_rules! debug {
    ($($args: tt)*) => { eprint!($($args)*) };
}

#[cfg(feature = "debug")]
macro_rules! debugln {
    ($($args: tt)*) => { eprintln!($($args)*) };
}

#[cfg(not(feature = "debug"))]
macro_rules! debug {
    ($($args:tt)*) => {};
}

#[cfg(not(feature = "debug"))]
macro_rules! debugln {
    ($($args:tt)*) => {};
}

macro_rules! vmax {
    ($x: expr, $y: expr) => { cmp::max($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::max($x, vmax!($($args),*)) };
}

macro_rules! vmin {
    ($x: expr, $y: expr) => { cmp::min($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::min($x, vmin!($($args),*)) };
}

fn main() {
    let n = parse_line::<usize>();
    let a = parse_vec::<u32>();

    let ans = a.iter().map(|&e| pow2_cnt(e)).sum::<u32>();
    println!("{}", ans);
}

fn pow2_cnt(mut x: u32) -> u32 {
    let mut cnt = 0;
    // x != 0
    while x % 2 == 0 {
        cnt += 1;
        x /= 2;
    }
    cnt
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        //
    }
}

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_owned()
}

fn read_word() -> String {
    const CAPACITY: usize = 16;

    let mut stdin = io::stdin();
    let mut byte: [u8; 1] = [0];

    loop {
        let mut buf = Vec::with_capacity(CAPACITY);

        loop {
            let res = stdin.read(&mut byte);

            if res.unwrap_or(0) == 0 || byte[0] <= b' ' {
                break;
            } else {
                buf.push(byte[0]);
            }
        }

        if !buf.is_empty() {
            return String::from_utf8(buf).unwrap();
        }
    }
}

fn parse_line<T: str::FromStr>() -> T {
    read_line().parse().ok().unwrap()
}

fn parse_word<T: str::FromStr>() -> T {
    read_word().parse().ok().unwrap()
}

fn parse_vec<T: str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn flush() {
    io::stdout().flush();
}

fn next_prime(x: i32) -> i32 {
    for i in (x + 1).. {
        if is_prime(i) {
            return i;
        }
    }

    panic!("attempt to add with overflow");
}

fn is_prime(x: i32) -> bool {
    let ceil = f64::from(x).sqrt().ceil() as i32;
    x == 2 || (2..(ceil + 1)).all(|i| x % i != 0)
}


Measured memory_bytes: 4352
import std.stdio;
import std.algorithm;
import std.string;
import std.range;
import std.array;
import std.conv;
import std.complex;
import std.math;
import std.ascii;
import std.bigint;
import std.container;
import std.typecons;


alias Tuple!(int, int, int) bar;
void main() {
	auto nma = map!(to!int)(readln().strip().split());
	while(nma[0]|nma[1]|nma[2]) {
		int n = nma[0];
		int m = nma[1];
		int a = nma[2];
		auto t = redBlackTree!(bar)();
		foreach(i; 0..m){
			auto hpq = map!(to!int)(readln().strip().split());
			int h = hpq[0];
			int p = hpq[1];
			int q = hpq[2];
			t.insert(bar(h,p,q));
		}
		foreach_reverse(b; t) {
			int p = b[1];
			int q = b[2];
			if(a == p || a == q) {
				a ^= p;
				a ^= q;
			}
		}
		writeln(a);
		nma = map!(to!int)(readln().strip().split());
	}
}

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

// macros
#define pb emplace_back
#define mk make_pair
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr)
#define whole(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bit(n) (1LL<<(n))
#define F first
#define S second
// functions
template <typename T> void unique(T& c){c.erase(std::unique(c.begin(), c.end()), c.end());}
template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;}
template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;}
template <typename T> ostream &operator<<(ostream &os, const vector<T>& vec){for(int i = 0; i < vec.size(); i++){ os << vec[i]; if(i + 1 != vec.size())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << "(" << p.first << ", " << p.second << ")"; return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << "(" << itr->first << ", " << itr->second << ")"; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const unordered_map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << "(" << itr->first << ", " << itr->second << ")"; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
//  types
using ll = long long int;
using P = pair<int, int>;
// constants
const int inf = 1e9;
const ll linf = 1LL << 60;
const double EPS = 1e-10;
const int mod = 1000000007;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
// io
struct fast_io{
  fast_io(){ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(20);}
} fast_io_;


int main(int argc, char const* argv[])
{
  string s, t; cin >> s >> t;
  int res = 0;
  rep(i, sz(s)){
    res += (s[i] != t[i]);
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3764
import itertools

n, m, x = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]

alg = [0]*m

l = range(n)

ans = 10**9
for i in range(1, n+1):
    for books in itertools.combinations(lst, i):
        alg = [0]*m
        money = 0
        for book in books:
            money += book[0]
            skills = book[1:]
            alg = [x+y for (x, y) in zip(alg, skills)]

        judge = True
        for i in alg:
            if i < x:
                judge = False

        if judge:
            if ans > money:
                ans = money

if ans == 10**9:
    print(-1)

else:
    print(ans)


Measured memory_bytes: 9232
n,m=map(int,input().split())

h=list(map(int,input().split()))
hills=[[-1]for _ in range(len(h))]
for i in range(len(h)):
    hills[i][0]=h[i]

for i in range(m):
    a,b=map(int,input().split())
    hills[a-1].append(hills[b-1][0])
    hills[b-1].append(hills[a-1][0])

ans = 0
for i in range(n):
    tower = hills[i][0]
    flag=False
    for enemy in hills[i][1:]:
        if enemy>=tower:
            flag=True
            break
    if flag == False:
        ans += 1

print(ans)

Measured memory_bytes: 26308
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=500010;

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

    ll a,b;cin>>a>>b;
    if(a==1||b==1){cout<<"1";return(0);}
    ll ans=0;
    ll bceil=b/2+b%2;
    ll bfloow=b/2;
    ans+=(a/2)*(bceil+bfloow);
    if(a%2){
        ans+=bceil;
    }
    cout<<ans;

	return(0);
}


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

using ll = long long;

template <typename T> T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;

int main() {
    int N, P;
    cin >> N >> P;
    vector<ll> dp(2);
    dp[0] = 1;
    for(int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        a %= 2;
        vector<ll> nxt = dp;
        for(int i = 0; i < 2; ++i) {
            nxt[(i + a) % 2] += dp[i];
        }
        dp = move(nxt);
    }
    cout << dp[P] << endl;
}


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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans;
    ans = max(a*b, c*d);
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define MOD 1000000007
#define SIZE 100005
#define FOR(i,a,n) for(i=(a);i<(n);i++)
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
int lower_bound(int a[],int n,int k){
	int left=-1; int right=n;
	while(right-left>1){
		int mid=(left+right)/2;
		if(a[mid]<=k) left=mid;
		else right=mid;
	}
	return right;
}
int a[100000],b[100000],c[100000];
ll cnt[100001];
int main(void)
{
	int n,id,i;
	ll res=0;
	scanf("%d",&n);
	FOR(i,0,n) scanf("%d",a+i);
	FOR(i,0,n) scanf("%d",b+i);
	FOR(i,0,n) scanf("%d",c+i);
	qsort(a,n,sizeof(int),comp);
	qsort(b,n,sizeof(int),comp);
	qsort(c,n,sizeof(int),comp);
	FOR(i,0,n){
		cnt[i]=n-lower_bound(c,n,b[i]);
	}
	for(i=n-2;i>=0;i--) cnt[i]+=cnt[i+1];
	FOR(i,0,n){
		id=lower_bound(b,n,a[i]);
		res+=cnt[id];
	}
	printf("%lld\n",res);
	return 0;
}
    

Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;cin >> n;
	vector<ll> a(n);
	vector<ll> b(n);
	rep(i,n) cin >> a.at(i) >> b.at(i);
	ll ans=0,j=0;
	for(int i=n-1;i>=0;--i){
		if((a[i]+j)%b[i]!=0){
			ans+=b[i]-(a[i]+j)%b[i];
			j+=b[i]-(a[i]+j)%b[i];
		}
	}
	cout << ans << endl;
}

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

using namespace std;

vector<int> parent, r, sz;
int ans;

int find_set(int a){
    if(a==parent[a]) return a;
    return parent[a]=find_set(parent[a]);
}

void union_sets(int a, int b){
    a=find_set(a), b=find_set(b);
    if(a!=b){
        if(r[a]<r[b]) swap(a, b);
        parent[b]=a;
        if(r[a]==r[b]) r[a]++;
        sz[a]+=sz[b];
        ans=max(ans, sz[a]);
    }
}

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

	int n, m;
	cin >> n >> m;
	parent=vector<int>(n);
	r=vector<int>(n, 0);
	sz=vector<int>(n, 1);
	ans=1;
	for(int i=0; i<n; i++) parent[i]=i;
	for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        x--, y--;
        union_sets(x, y);
	}
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 5512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

int main()
{
    int n;
    string s;
    cin >> n >> s;
    int left = 0;
    int addleft = 0;
    for (int i = 0; i < n; i++)
    {
        if ('(' == s[i])
        {
            left++;
        }
        else
        {
            if (left > 0)
            {
                left--;
            }
            else
            {
                addleft++;
            }
        }
    }
    string addstr1 = "", addstr2 = "";
    for (int i = 0; i < addleft; i++)
    {
        addstr1 += '(';
    }
    for (int i = 0; i < left; i++)
    {
        addstr2 += ')';
    }
    string ans = addstr1 + s + addstr2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3608
a2=int(input())
a=0
b3=0
for i in range(a2):
    b2,c2=map(str,input().split())
    b=int(b2)
    c=int(c2)
    if b==c:
        a+=1
        if a==3:
            b3=1
            continue
    else:
        a=0
        
if b3>0:
    print('Yes')
if b3==0:
    print('No')

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

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    int zero = 0, one = 0;

    rep(i, n)
    {

        if (s[i] == '0')
            zero += 1;
        else
            one += 1;
    }

    cout << n - (abs(zero - one)) << endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main()
{
    string r, a;
    while(cin >> r >> a && r != "0" && a != "0") {
        int hist1[10], hist2[10];
        memset(hist1, 0, sizeof(hist1));
        memset(hist2, 0, sizeof(hist2));
        
        int hit = 0;
        for(int i = 0; i < 4; i++) {
            hist1[r[i] - '0']++;
            hist2[a[i] - '0']++;
            if(r[i] == a[i]) {
                hit++;
            }
        }
        
        int blow = 0;
        for(int i = 0; i < 10; i++) 
            if(hist2[i] > 0 && hist1[i])
                blow += (hist2[i] > hist1[i]) ? hist1[i] : hist2[i];
        blow -= hit;
        
        cout << hit << " " << blow << endl;
    }   
}

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

#define i64 long long int
#define ran 101101

int n, m;
pair<int, int> a[ran];

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0;i<n;i++) scanf("%d%d", &a[i].first, &a[i].second);
	sort(a, a+n);
	
	i64 ans = 0;
	for(int i=0;i<n && m>0;i++) {
		int det = min(m, a[i].second);
		ans += 1LL*det*a[i].first;
		m-=det;
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 1024
#![allow(non_snake_case)]
use proconio::{input, fastout};
use proconio::marker::Usize1;

#[fastout]
fn main() {
    input!{
        R:usize, C:usize, K:usize,
        mut items: [(Usize1, Usize1, i64); K] 
    }
    items.sort();
    items.push((R, C, 0));
    let mut idx = 0;
    let mut prv = vec![vec![0i64; 4]; C];
    let mut nxt = vec![vec![0i64; 4]; C];
    let mut v: i64 = 0;
    let mut f: bool;
    for i in 0..R {
        for j in 0..C {
            f = false;
            let &t = prv[j].iter().max().unwrap();
            if items[idx].0 == i && items[idx].1 == j {
                f = true;
                v = items[idx].2;
                idx += 1;
                // println!("{} {} {}", i, j, v);
            }
            for k in 0..4{
                nxt[j][k] = t;
                if j > 0 && nxt[j][k] < nxt[j-1][k] {
                    nxt[j][k] = nxt[j-1][k];
                }
                if f && k > 0{
                    if nxt[j][k] < t + v {
                        nxt[j][k] = t + v;
                    }
                    let p = if j > 0 {nxt[j-1][k-1]} else {0};
                    if nxt[j][k] < p + v {
                        nxt[j][k] = p + v;
                    } 
                }
            }
        }
        std::mem::swap(&mut prv, &mut nxt);
        // println!("{:?}", prv)
    }
    println!("{}", prv[C-1].iter().max().unwrap())
}


Measured memory_bytes: 12508
N = int(input())
Prime = {}
mod = 7 + 10**9

if N > 2:
    Prime[2] = 1
    for i in range(3, N+1):
        M = i
        newPrime = True
        for j in Prime:
            if M % j == 0:
                newPrime = False
                while M % j == 0:
                    M //= j
                    Prime[j] += 1
        if newPrime:
            Prime[i] = 1
    
    ans = 1
    for p in Prime:
        ans *= Prime[p] + 1
        ans %= mod
    print(ans)

else:
    print(N)

Measured memory_bytes: 3064