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

public class Main {
    private static List<Long> sums;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long M = sc.nextLong();
//        int[] A = new int[N];
//        for(int i=0;i<N;i++){A[i]=sc.nextInt();}
        sums = new ArrayList<>(N);
        List<Long> A = Stream.generate(sc::nextLong)
                .limit(N)
                .sorted()
                .collect(Collectors.toList());
        long nowSum = 0;
        for(int i=A.size()-1;i>=0;i--){
            nowSum += A.get(i);
            sums.add(nowSum);
        }

        long l=0;
        long r=10_000_000_000_000_000L;
        while(l<r){
            long m = (l+r)/2;
//            System.out.println(m + ":"+getTotalNumOver(A, m));
            if(getTotalNumOver(A, m) > M){
                l = m+1;
            }else{
                r = m;
            }
        }
        long cnt = getTotalNumOver(A,l);
        final long tgtSum = l;
        long sum = 0;
        sum += (l-1) * (M-cnt);

//        assert(getSumOver(A, 67, 34) == 135);
//        assert(getSumOver(A, 67, 10) == 0);
        //l以上な和をすべて足したもの。
        sum += A.stream().mapToLong(
                p->getSumOver(A, tgtSum, p)
        ).sum();
        System.out.println(sum);
    }

    private static long getSumOver(List<Long> lst, long maxsum, long p){
        long tgt = maxsum-p;
        int l=0;
        int r=lst.size()-1;
        while(l<r){
            int m=(l+r)/2;
            if(tgt > lst.get(m)){
                l = m+1;
            }else{
                r = m;
            }
        }
        if(tgt > lst.get(l)){
            return 0;
        }
        return getSumAft(lst, l) + p * (lst.size()-l);

    }
    private static long getSumAft(List<Long> lst, int ind){
        //returns sum after index inclusive.
        return sums.get(lst.size()-ind-1);
    }

    private static long getTotalNumOver(List<Long> lst, long tgt){
        return lst.stream().mapToLong(
                p -> getCountOver(lst, tgt - p)
        ).sum();
    }

    private static long getCountOver(List<Long> lst, long tgt){
        int l=0;
        int r=lst.size()-1;
        while(l<r){
            int m=(l+r)/2;
            if(tgt > lst.get(m)){ // tgt > lst[m]
                l=m+1;
            }else{
                r=m;
            }
        }
        if(tgt > lst.get(l)){
            return 0;
        }else {
            return lst.size()-l;
        }
    }
}


Measured memory_bytes: 65048
// 2020-07-24 06:58:30
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<vector<int> > dp(n+1, vector<int>(n+1, 0));
  int ans = 0;
  REP(i, 0, n-1) REP(j, i+1, n) {
    if(s[i] == s[j]) dp[i+1][j+1] = min(j-i, dp[i][j]+1);
    chmax(ans, dp[i+1][j+1]);
  }
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 101076
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

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

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

const int INF=5e8;
struct segtree{
  int val[1100000];//maxi
  int lazy[1100000];
  int n;
  void init(int n_){
    n=1;
    while(n<n_) n<<=1;
    CLR(val);
    CLR(lazy);
  }
  void push(int i){
    if(lazy[i]){
      lazy[i*2+1]+=lazy[i];
      lazy[i*2+2]+=lazy[i];
      val[i*2+1]+=lazy[i];
      val[i*2+2]+=lazy[i];
      lazy[i]=0;
    }
  }
  int query(int i,int l,int r){//find 10 in most left position
    if(val[i]<10) return INF;
    if(r-l==1) return l;
    push(i);
    int md=(l+r)>>1;
    int L=query(i*2+1,l,md);
    if(L!=INF) return L;
    return query(i*2+2,md,r);
  }
  void add(int a,int b,int i,int l,int r,int v){
    if(a<=l && r<=b){
      lazy[i]+=v;
      val[i]+=v;
      return;
    }
    if(b<=l || r<=a) return;
    int md=(l+r)>>1;
    push(i);
    add(a,b,i*2+1,l,md,v);
    add(a,b,i*2+2,md,r,v);
    val[i]=max(val[i*2+1],val[i*2+2]);
  }
};
segtree seg;
char s[500005];
lint ar[500005];
int n;


int main(){
  scanf("%s",s);
  n=strlen(s);
  REP(i,n) ar[i]=s[i]-'0';
  seg.init(n);

  lint last=ar[n-1];
  lint res=ar[n-1];
  for(int i=n-2;i>=0;--i){
    if(ar[i]>last){
      int P=seg.query(0,0,seg.n);
      if(P==INF){
        if(i<n-2) seg.add(n-2,n-1,0,0,seg.n,1);
        res+=10;
      }else{
        if(P>i+1) seg.add(P-1,P,0,0,seg.n,1);
        seg.add(P,P+1,0,0,seg.n,-10);
      }
      if(P==i+1 || i==n-2) seg.add(i,i+1,0,0,seg.n,last+10-(ar[i]-1));
      else seg.add(i,i+1,0,0,seg.n,last+9-(ar[i]-1));
      last=ar[i]-1;
    }else{
      seg.add(i,i+1,0,0,seg.n,last-ar[i]);
      last=ar[i];
    }
  }
  res=(res+8)/9;
  cout<<res<<endl;
  return 0;
}





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

int main()
{
  int n;
  cin >> n;
  unordered_map<int, int> mp;
  for (int i = 0; i < n; ++i)
  {
    int a;
    cin >> a;
    if (mp[a] > 0)
      mp[a]--;
    else
      mp[a]++;
  }
  int cnt = 0;
  for (auto &e : mp)
    if (e.second > 0)
      cnt++;

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

Measured memory_bytes: 4388
for i in range(1, 3005):
    x = input().split(" ")
    a = int(x[0])
    b = int(x[1])
    if a + b == 0:
        break
    if a < b:
        print(str(a) + " " + str(b))
    else:
        print(str(b) + " " + str(a))

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

#define ll long long
#define pb push_back

vector<int>g[100003];
vector<int>v(100003);
queue<int>q;

int main()
{
    ll n,k;
    cin>>n>>k;

    ll a;
    ll c=0;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        if(a>=k)
        {
            c++;
        }
    }
    cout<<c<<endl;



}











Measured memory_bytes: 2944
n, k = map(int, input().split())
arr = list(map(int, input().split()))
expected = []
cumsum = []
for x in arr:
	sum = (x * (x + 1)) // 2
	ex = sum / x
	expected.append(ex)

sum = 0
maxi = 0
taken = 0
bad = 0
for x in expected:
	sum += x
	taken += 1
	if taken == k:
		 maxi = max(maxi, sum)
	elif taken > k:
		sum -= expected[bad]
		bad += 1
		maxi = max(maxi, sum)
print(maxi)

Measured memory_bytes: 98992
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

class program{
    public static void Main(){
        var nums = Console.ReadLine().Split(' ').Select(_ => int.Parse(_)).ToList();
        var dice = new Dice(nums);
        var dirs = Console.ReadLine();
        foreach(var dir in dirs){
            dice.Rotate(dir);
        }
        Console.WriteLine(dice.faces.First(_ => _.dir == 'T').num);
    }
}

class Dice{
    public List<Face> faces = new List<Face>(6);

    public Dice(List<int> nums){
        faces.Add(new Face(nums[0],'T'));
        faces.Add(new Face(nums[1],'S'));
        faces.Add(new Face(nums[2],'E'));
        faces.Add(new Face(nums[3],'W'));
        faces.Add(new Face(nums[4],'N'));
        faces.Add(new Face(nums[5],'B'));
    }

    public void Rotate(char dir){
        if(dir == 'N'){
            var tmpnum = getFace('T').num;
            getFace('T').num = getFace('S').num;
            getFace('S').num = getFace('B').num;
            getFace('B').num = getFace('N').num;
            getFace('N').num = tmpnum;
        }
        if(dir == 'W'){
            var tmpnum = getFace('T').num;
            getFace('T').num = getFace('E').num;
            getFace('E').num = getFace('B').num;
            getFace('B').num = getFace('W').num;
            getFace('W').num = tmpnum;
        }
        if(dir == 'S'){
            var tmpnum = getFace('T').num;
            getFace('T').num = getFace('N').num;
            getFace('N').num = getFace('B').num;
            getFace('B').num = getFace('S').num;
            getFace('S').num = tmpnum;
        }
        if(dir == 'E'){
            var tmpnum = getFace('T').num;
            getFace('T').num = getFace('W').num;
            getFace('W').num = getFace('B').num;
            getFace('B').num = getFace('E').num;
            getFace('E').num = tmpnum;
        }
    }

    public Face getFace(char d){
        return faces.First(_ => _.dir == d);
    }
}

class Face{
    public int num;
    public char dir;

    public Face(int n, char d){
        num = n;
        dir = d;
    }
}



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

int dp[100007][3];

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

    for (int i = 0; i < n; i++) {
        vector<int> store(3);
        for (auto &x : store) cin >> x;

        for (int j = 0; j < 3; j++) {
            if (i == 0) {
                dp[i][0] = store[0];
                dp[i][1] = store[1];
                dp[i][2] = store[2];
            }
            else {
                for (int k = 0; k < 3; k++) { ///previous day er sobgulor songe bortoman day te ja paisi ta die update(sudumatro prv day ar bortoman day mile gele continue
                    if (j == k) continue;
                    dp[i][j] = max(dp[i][j], dp[i-1][k] + store[j]);
                }
            }
        }
    }

    cout << max({dp[n-1][0], dp[n-1][1], dp[n-1][2]});
}


Measured memory_bytes: 1408
s = input()
n = len(s)

if s[:(n-1)//2] == ''.join(reversed(s[:(n-1)//2])) and s[((n+3)//2-1):] == ''.join(reversed(s[((n+3)//2-1):])) and s[:(n-1)//2] == s[((n+3)//2-1):]:
  print("Yes")
else:
  print("No")

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

using namespace std;

int n,m;
char s[1200];

int main(){
	scanf("%s%d",s+1,&m); n=strlen(s+1);
	for (int i=1;i<=n;++i)
		if ((i-1)%m==0) putchar(s[i]);
	puts("");
	
	return 0;
}
			

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

int m,n;
char s1[105],s2[105];
string rs="";

int main()
{
    cin>>s1+1>>s2+1;
    m=strlen(s1+1);
    n=strlen(s2+1);
    for(int i=n;i<=m;i++)
    {
        int tmp=1;
        bool check=false;
        for(int j=i-n+1;j<=i;j++)
            if(s1[j]!='?'&&s1[j]!=s2[tmp])
            {
                check=true;
                break;
            }
            else
                tmp++;
        if(check==false)
        {
            string ss="";
            for(int j=1;j<=i-n;j++)
                if(s1[j]=='?')
                    ss+='a';
                else
                    ss+=s1[j];
            tmp=1;
            for(int j=i-n+1;j<=i;j++)
                ss+=s2[tmp++];
            for(int j=i+1;j<=m;j++)
                if(s1[j]=='?')
                    ss+='a';
                else
                    ss+=s1[j];
            if(rs==""||rs>ss)
                rs=ss;
        }
    }
    if(rs=="")
        cout<<"UNRESTORABLE";
    else
        cout<<rs;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n;
        
        while ((n = sc.nextInt())!=0){
            int sum = 0;
            int max=0,min=1000;
            for(int i=0;i<n;i++){
                int num = sc.nextInt();
                sum += num;
                if(max<num) max=num;
                if(min>num) min=num;
            }
            sum -= max;
            sum -= min;
            
            System.out.println(sum/(n-2));
        }
        
    }
}

Measured memory_bytes: 29340
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b;
    cin >> a >> b;
    cout << (a-1)*(b-1) << "\n";
    return 0;
}

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

#define ll long long
using namespace std;

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> ban(h);
    for (int i = 0; i < h; i++)cin >> ban[i];

    vector<vector<ll>> O(h, vector<ll>(w + 1));
    for (int i = 0; i < h; i++) {
        for (int j = w; j > 0; j--) {
            O[i][j - 1] = O[i][j] + (ban[i][j - 1] == 'O');
        }
    }
    vector<vector<ll>> I(h + 1, vector<ll>(w));
    for (int i = h; i > 0; i--) {
        for (int j = 0; j < w; j++) {
            I[i - 1][j] = I[i][j] + (ban[i - 1][j] == 'I');
        }
    }

    ll ret = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (ban[i][j] == 'J')ret += O[i][j] * I[i][j];
        }
    }

    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 164632
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b,c,d,e,n;
  string s,ss,sss;
  cin>>s;
  ll ans=0;
  for(int i=0;i<s.size()/2;i++){
    if(s[i] != s[s.size()-i-1])ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
/*
Created on Thu Aug 27 21:32:39 2020

@author: roastedcoder

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
const int mod = 1e9+7;
const int INF = INT_MAX;
#define endl "\n"
#define append push_back
#define roastedcoder ios_base::sync_with_stdio(false); cin.tie(NULL);
//__________________________________________________________________


int main() {
	roastedcoder
	int d, t, s; cin>>d>>t>>s;
	double tmp = 1.0*d/s;
	t<tmp ? cout<<"No" : cout<<"Yes";
}

//__________________________________________________________________
/*
Sample Input:


Sample Output:


*/

Measured memory_bytes: 3648
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef pair<ll, ll> pll;

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

template <class T>
inline double eucladian(T ax, T ay, T bx, T by) { return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by)); }

vector<pll> engines;
int n;

void init()
{
	cin >> n;
	int zr = 0;
	REP(_i, n)
	{
		ll x, y; cin >> x >> y;
		if (!x && !y) // remove (0, 0)
		{
			++zr; continue;
		}
		engines.PB(pll(y, x));
	}

	n -= zr; // remove (0, 0)

	// sort by angle : use atan2 in <cmath>
	// theta = atan2(y,x)
	sort(ALL(engines), [](pll& left, pll& right){ return atan2(left.first, left.second) < atan2(right.first, right.second); });
}

int main()
{
	init();

	double ans = 0;

	REP1C(k, n) // how many engines ?
	{
		REP(i, n) // choose engines start idx
		{
			ll vx = 0, vy = 0;
			for (int j = i; j < min(n, i + k); ++j)
			{
				vy += engines[j].first;
				vx += engines[j].second;
			}

			if (n - i < k) // if not enough engines
			{
				for (int j = 0; j < (k - (n - i)); ++j)
				{
					vy += engines[j].first;
					vx += engines[j].second;
				}
			}
			chmax(ans, eucladian((ll)0, (ll)0, vx, vy));
		}
	}

	cout << setprecision(21) << ans << endl;
}


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

int main(){
    int N;
    cin >> N;
    if(N % 2 == 0){
        int t = N / 2;
        cout << (double) t / N << endl;
    } 
    else{
        int t = (N + 1) / 2;
        cout << (double) t / N << endl;
    } 
}

Measured memory_bytes: 256
from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if s[y][x]!='.':
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H:
            q_append((nx,ny,l+1))
else:
    print(-1)

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

int main()
{
    int n;
    cin >> n;
    int sum = 0;
    int ma = 0;
    for(int i=0; i<n; i++){
        int c;
        cin >> c;
        ma = max(ma,c);
        sum += c;
    }
    cout << sum - ma/2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdint>
 
using namespace std;
 
char next(char before, char now, char ans)
{
	auto inv = [](char animalType){ return animalType == 'S' ? 'W' : 'S'; };
	char result{ before };
 
	if(ans != 'o') {
		result = inv(result);
	}
 
	if(now != 'S') {
		result = inv(result);
	}
 
	return result;
}
 
bool judge(string& str, string& ans)
{
	for(auto i = 1; i < str.size() - 1; ++i) {
		str[i + 1] = next(str[i - 1], str[i], ans[i - 1]);
	}
 
	return (str[0] == str[str.size() - 2]) && (str[1] == str[str.size() - 1]);
}
 
int main()
{
	int_least32_t n;
	cin >> n;
	
	string input;
	cin >> input;
 
	string result(n + 2, 'S');
	char ini[] = { 'S', 'W' };
	bool flag{ false };
	for(auto i = 0; i < 2 && flag == false; ++i) {
		result[0] = ini[i];
		for(auto j = 0; j < 2 && flag == false; ++j) {
			result[1] = ini[j];
			flag = judge(result, input);
		}
	}
 
	if(flag) {
		cout << result.substr(1, n) << endl;
	}
	else {
		cout << -1 << endl;
	}
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> P;
typedef priority_queue<P,vector<P>,greater<P>> P_queue;

#define REP(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define ALL(a) a.begin(),a.end()
#define SORT(a) sort(ALL(a))
#define U_ERASE(V) V.erase(unique(ALL(V)), V.end());

const ll MOD=998244353;
const ll mod=1000000007;
const ll INF=1e15;
vec dx={1,0,-1,0};
vec dy={0,1,0,-1};

vec d;
ll memo[200010];
bool used[200010];
ll Loop;
ll Solve(ll x, ll K){
    
    //cout<<K<<' '<<memo[x]<<' '<<x<<endl;
    if(K==0) return x;
    if(!used[x]) {
        memo[x]=K;
        used[x]=true;
        return Solve(d[x],K-1);
    }
    if(K>=memo[x]-K) {
        Loop=memo[x]-K;
        return Solve(x,K%Loop);
    }
    return Solve(d[x],K-1);
}
void init(){
    rep(i,200010) memo[i]=INF;
    rep(i,200010) used[i]=false;
    return;
}

int main(){
    init();
    ll N,K; cin>>N>>K;  
    rep(i,N){
        ll x; cin>>x; x--;
        d.pb(x);
    }
    
    cout<<Solve(0,K)+1<<endl;

}

Measured memory_bytes: 7080
let () = Scanf.scanf "%d %d\n" @@ fun d g ->
  let pcs = Array.init d @@ fun _ ->
    Scanf.scanf "%d %d\n" @@ fun p c -> p, c in
  let n = Array.fold_left ( + ) 1 (Array.map fst pcs) in
  let dp = Array.make n 0 in
  Array.iteri (fun i (p, c) ->
    for j = n - 1 downto 0 do
      dp.(j) <-
        Array.fold_left max min_int @@ Array.init (p + 1) @@ fun k ->
        try dp.(j - k) + 100 * (i + 1) * k + if k = p then c else 0 with _ -> min_int
    done) pcs;
  try
    for i = 0 to n - 1 do
      if g <= dp.(i) then (Printf.printf "%d\n" i; raise Not_found)
    done
  with Not_found -> ()

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define eps 1e-10
using namespace std;
class Point {
public:
	double x,y;
	Point(double x=0, double y=0):x(x),y(y){}
	Point operator+ (Point p) { return Point(x+p.x,y+p.y); }
	Point operator- (Point p) { return Point(x-p.x,y-p.y); }
	Point operator* (double a) { return Point(x*a,y*a); }
	Point operator/ (double a) { return Point(x/a,y/a); }
	double abs() { return sqrt(norm()); }
	double norm() { return x*x+y*y; }
	bool operator< (const Point& p) const { return x!=p.x?x<p.x:y<p.y; }
	bool operator== (const Point& p) const { return fabs(x-p.x)<eps&&fabs(y-p.y)<eps; }
};
typedef Point Vector;
double dot(Vector a, Vector b) { return a.x*b.x+b.y*a.y; }
double cross(Vector a, Vector b) { return a.x*b.y-a.y*b.x; }
bool equal(double a, double b) {
	return fabs(a-b)<eps;
}
int main() {
	int n;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);		
	cin>>n;
	for (int i=0; i<n; ++i) {
		double x0,y0,x1,y1,x2,y2,x3,y3;
		cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
		Point a(x0,y0);
		Point b(x1,y1);
		Point c(x2,y2);
		Point d(x3,y3);
		if (equal(dot(b-a,d-c),0.0)) cout<<1<<endl;
		else if (equal(cross(b-a,d-c),0.0)) cout<<2<<endl;
		else cout<<0<<endl;
	}
	return 0;
} 


Measured memory_bytes: 3308
import bisect

N=int(input())
city=[]
for i in range(N):
    x,y,p=map(int,input().split())
    city.append((x,y,p))

xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[j][1]) for j in range(N)] for i in range(2**N)]

for i in range(2**N):
    X=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            X.append(city[j][0])
            xx[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in X:
            res=min(res,abs(city[j][0]-k))
        xx[i][j]=res

for i in range(2**N):
    Y=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            Y.append(city[j][1])
            yy[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in Y:
            res=min(res,abs(city[j][1]-k))
        yy[i][j]=res

ans=[10**15 for i in range(N+1)]
for i in range(2**N):
    cond=i
    rest=[j for j in range(N) if i>>j &1==0]
    count=N-len(rest)
    while True:
        X=cond
        Y=i-cond
        temp=0
        for j in rest:
            temp+=min(xx[X][j],yy[Y][j])*city[j][2]
        ans[count]=min(ans[count],temp)
        if cond==0:
            break
        else:
            cond=(cond-1)&i

for i in range(N+1):
    print(ans[i])


Measured memory_bytes: 83912
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
using namespace std;
//using namespace boost::multiprecision;

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}


int main(){
  
  long long a,b;
  cin>>a>>b;
  long long ans = lcm_(a,b);
  cout<<ans<<endl;
  return 0; 
}


Measured memory_bytes: 256
#include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 100050;
    int main()
    {
        ll a,b;
        cin>>a>>b;
        ll cnt = 1;
        while(a--)
        {
            cnt *=100;
        }
        b = b + b/100;
        cout<<cnt* b<<endl;
        return 0;
    }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n,i,a[1000000],x;
int main()
{
    cin>>n;
    for (i=1;i<=n-1;i++)
    {
        cin>>x;
        a[x]++;
    }
    for (i=1;i<=n;i++)
        cout<<a[i]<<endl;
}


Measured memory_bytes: 5184
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        long a =sc.nextLong();
        long b =sc.nextLong();
        long k = sc.nextLong();

        if( k <= a ) {
            System.out.println( a - k + " " + b );
        }
        else if( k <= a + b ) {
            System.out.println( "0 " + ( b - ( k - a ) ) );
        }
        else {
            System.out.println( "0 0" );
        }
    }
}


Measured memory_bytes: 38932
import java.util.Scanner;

public class Main {
	//half and half


	public static void main(String[] args){
		int r,D,x;
		Scanner sc = new Scanner(System.in);
		r=sc.nextInt();
		D=sc.nextInt();
		x=sc.nextInt();
		for(int i=1;i<=10;i++) {
			x=r*x-D;
			System.out.println(x);
		}
	}
}

Measured memory_bytes: 21588
import sys
input=lambda: sys.stdin.readline().rstrip()
k=int(input())
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
def ggcd(a,b,c):
  return gcd(gcd(a,b),c)
ans=0
for a in range(k):
  for b in range(k):
    for c in range(k):
      ans+=ggcd(a+1,b+1,c+1)
print(ans)

Measured memory_bytes: 74136
//#define local
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i,n); for(long long i = 0;i < (n);i++)
using ll = long long;
using P = pair<long long,long long>;
template <class T> using vec = vector<T>;
#ifdef local
#include "debug.cpp"
#else
#define debug(...)
#endif
const ll mod = 1e9+7;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout << fixed << setprecision(10);
    ll s; cin >> s;
    ll dp[2005];
    rep(i,2005)dp[i] = 1;
    rep(i,3)dp[i] = 0;
    for(int i = 3;i<=s;i++){
        rep(j,i-2){
            dp[i] += dp[j];
            dp[i] %= mod;
       }   
    }
    cout << dp[s] << endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
vector<int> r,p;
void init(int size){
  r.resize(size,0);
  p.resize(size,0);
  for(int i=0;i<size;i++) r[i]=0,p[i]=i;
}

int find(int x){
  if(x!=p[x]) p[x]=find(p[x]);
  return p[x];
}

bool same(int x,int y){
  return find(x)==find(y);
}
void unite(int x,int y){
  x=find(x);y=find(y);
  if(x==y) return;
  if(r[x]>r[y]) {
    p[y]=x;
  }else {
    p[x]=y;
    if(r[x]==r[y]) r[y]++;
  }
}

int main(){
  int n,m,i,j,k,l;
  cin>>n>>m;
  init(n+m);
  for(i=0;i<n;i++){
    cin>>k;
    for(j=0;j<k;j++){
      cin>>l;
      unite(i,n+l-1);
    }
  }
  bool f = true;
  for(i=0;i<n;i++) {
    f&=same(0,i);
  }
  cout << (f?"YES":"NO") << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (int)(n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
    x = 0; char c = getchar(); int f = 0;
    for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}
namespace {
    const int mo = 1e9 + 7;
    inline int add(int x, int y) { x += y; return x >= mo ? x - mo : x; }
    inline int sub(int x, int y) { x -= y; return x < 0 ? x + mo : x; }
    inline int mul(int x, int y) { return (lo) x * y % mo; }
    inline int power(int a, int k = mo - 2) {
		int ans = 1;
		for (; k; k >>= 1, a = mul(a, a))
			if (k & 1) ans = mul(ans, a);
		return ans;
    }
	inline void U(int &x, int y) { x = add(x, y); } 
}

const int N = 3e5 + 233; 
int n, a[N], id[N], rnk[N], val[N], pre[N], pid[N], sum[N], isum[N];

struct bit_t {
	int tr[N];
	inline void init() {
		memset(tr, 0, sizeof tr);
	}
	inline void add(int x, int v) {
		for (; x < N; x += x & -x) U(tr[x], v);
	}
	inline int _query(int x) {
		if (x <= 0) return 0;
		int ans = 0;
		for (; x >= 1; x -= x & -x) U(ans, tr[x]);
		return ans;
	}
	inline int query(int l, int r) {
		return l > r ? 0 : sub(_query(r), _query(l - 1));
	}
} L, R;

int main(void) {
	read(n);
	rep (i, n) read(a[i]), id[i] = i;
	sort(id + 1, id + n + 1, [](int x, int y) {
			return a[x] < a[y];
		});
	rep (i, n) rnk[id[i]] = i;
	rep (k, n) val[k] = mul(a[id[k]] - (k - 1) - 1, power(a[id[k]] - (k - 1)));
	rep (i, n) isum[i] = power(sum[i] = mul(sum[i - 1] == 0 ? 1 : sum[i - 1], val[i]));
	rep (i, n) pre[i] = val[i] == 0 ? i : pre[i - 1];
	rep (i, n) pid[i] = a[id[i]] == a[id[i - 1]] ? pid[i - 1] : i - 1;
	int all = 1;
	rep (i, n) {
		if (a[i] - (rnk[i] - 1) <= 0)
			return puts("0"), 0;
		all = mul(all, a[i] - (rnk[i] - 1));
	}
	int aa = 0, bb = 0, cc = 0;
	map <int, int> mp;
	rep (i, n) mp[a[i]]++;
	// a[i] == a[j]
	for (auto i : mp) U(aa, mul((lo) i.second * (i.second - 1) / 2, mul(power(2), all)));

	// rep (i, n) cerr << sum[i] << " \n"[i == n];
	
	int coef = 0, tot = 0;
	L.init(); R.init();
	for (int i = n; i >= 1; i--) {
		int u = rnk[i];
		int tmp = mul(sum[u - 1], L.query(pre[u - 1] + 1, pid[u]));
		U(coef, mul(tmp, power(a[i] - (u - 1))));
		L.add(u, mul(isum[u], a[i] - u));
		U(tot, R.query(1, pid[u]));
		R.add(u, 1);
	}
	bb = mul(all, sub(tot, mul(power(2), coef)));

	L.init();
	coef = 0;
	for (int i = 1; i <= n; i++) {
		int u = rnk[i];
		int tmp = mul(sum[u - 1], L.query(pre[u - 1] + 1, pid[u]));
		U(coef, mul(tmp, power(a[i] - (u - 1))));
		L.add(u, mul(isum[u], a[i] - u));
	}
	cc = mul(coef, mul(power(2), all));

	// cerr << bb << " " << cc << " " << aa << "\n";
	cout << add(add(aa, bb), cc) << "\n";
}


Measured memory_bytes: 20608
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
int main()
{
	string str;
	cin>>str;
	bool f=false;
	for(int i=0;i<str.size()-1;i++)
	{
		if(str[i]!=str[i+1])
		{
			f=true;
			break;
		}
	}
	if(f)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var a []int
	for i := 0; i < 3; i++ {
		var tmp int
		fmt.Scan(&tmp)
		a = append(a, tmp)
	}

	sort.Ints(a)
	diff := 0
	for i := 2; i > 0; i-- {
		diff += a[i] - a[i-1]
	}
	fmt.Println(diff)
}


Measured memory_bytes: 512
#include <stdio.h>

int main(void){
	int W,H,x,y,r;
	scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
	if(x>=r&&y>=r&&(H-r)>=y&&(W-r)>=x){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <bitset>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <iomanip>
 
using namespace std;
  
/********** TEMPLATE STARTS HERE ***********/
    
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define pb push_back
#define test int t; cin >> t; while(t--)
#define skip continue
#define stop break
#define sz(v) (int)v.size()
#define endl '\n'
#define PI 3.1415926535897932384626433832795
#define EPS 1e-9
#define gcd __gcd 
#define mp make_pair
#define debug(a) cout << #a << ": " << a << endl
#define debug1(a, l, r) FR(i, l, r) cout << a[i] << " "; cout << endl
#define SET(a, b) memset(a, b, sizeof(a));
#define refresh fflush(stdout);
#define digits(n) (int)(log10(n) + 1)
  
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <long long> vl;
typedef vector <pii> vii;
typedef vector <pll> vll;
    
const int INF = 0x3f3f3f3f;
const int LINF = 0x3f3f3f3f3f3f3f3f;
    
template <typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template <typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
   
/*********** TEMPLATE ENDS HERE *************/

ll GCd = 1;

main()
{
	IOS
	
	ll n, m;
	cin >> n >> m;
	
	if(n == 1)
	{
		cout << m;
		return 0;
	}
	
	for(ll i = 2; (i + 1) * (i + 1) <= m; i++)
		if(m % i == 0)
		{
			if(m / i >= n)
				amax(GCd, i);
			if(i >= n)
				amax(GCd, m / i);
		}
	cout << GCd;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N,M;

signed main(){
	cin>>N>>M;
	int n=ceil2(N,2);
	int m=ceil2(M,2);
	int n2=N/2;
	int m2=M/2;
	if(N==1||M==1){
		cout<<1<<endl;
	}
	else{
		cout<<n*m+n2*m2<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
def test(array: list, array_list: list, N: int):
    if len(array) == N:
        array_list.append(array)
        return
    new_array = array[:]
    new_array.append(0)
    array.append(1)
    test(new_array, array_list, N)
    test(array, array_list, N)


N, M = map(int, input().split())

# 組み合わせ作成
array_list = []
array = []
test(array, array_list, N)

# 各行のスイッチ
switches_list = []
for i in range(M):
    line = input().split()
    switch_count = int(line[0])
    switches = [0] * N
    for j in range(switch_count):
        switches[int(line[j + 1]) - 1] = 1
    switches_list.append(switches)
# print(switches_list)

# 余り
surpluses = input().split()

count = 0
for array in array_list:
    for i in range(len(switches_list)):
        switches = switches_list[i]
        surplus = int(surpluses[i])
        on_count = 0
        for j in range(len(switches)):
            if switches[j] == 1 and array[j] == 1:
                on_count += 1
        if on_count % 2 != surplus:
            break
        # 全電球分のチェックを通ったらOKとする
        if i == len(switches_list) - 1:
            count += 1
print(count)


Measured memory_bytes: 3188
N,M,X,Y = map(int,input().split())
xs = list(map(int,input().split()))
ys = list(map(int,input().split()))
mx = max(xs)
my = min(ys)

for z in range(X+1,Y+1):
    if mx < z <= my:
        print('No War')
        exit()
print('War')


Measured memory_bytes: 3060
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <string>

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

    std::string S;
    int64_t K;
    std::cin >> S;
    std::cin >> K;

    char first_non_one = '1';
    int64_t first_non_one_idx = 0;
    for(int64_t i = 0; i < (int64_t)S.size(); i++){
        if(S[i] != '1'){
            first_non_one = S[i];
            first_non_one_idx = i;
            break;
        }
    }

    if(K > first_non_one_idx){
        std::cout << first_non_one << std::endl;
    }
    else{
        std::cout << 1 << std::endl;
    }
    return 0;

}


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

int main(){
  int N,M;
  cin >> N >> M;
  if(N==M) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0; 
}

Measured memory_bytes: 3636
fun main(args: Array<String>) {
    val array = IntArray(readLine()?.toInt()?.plus(1) ?: 0)
    readLine()?.split(" ".toRegex())
        ?.map(String::toInt)
        ?.forEachIndexed { index, value ->
            array[index + 1] = value
        }
    for(i in 1..array.lastIndex) {
        println("node $i: key = ${array[i]}, ${if (i != 1) {
            "parent key = ${array[parent(i)]}, "
        } else {
            ""
        }
        }${if (left(i) <= array.lastIndex) {
            "left key = ${array[left(i)]}, "
        } else {
            ""
        }
        }${if (right(i) <= array.lastIndex) {
            "right key = ${array[right(i)]}, "
        } else {
            ""
        }
        }")
    }
}

fun parent(index: Int) = index / 2
fun left(index: Int) = index * 2
fun right(index: Int) = index * 2 + 1


Measured memory_bytes: 29488
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

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; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()





int main() {
    int r, g, b;
    cin >> r >> g >> b;
    bool flag = true;
    int k;
    cin >> k;
    while (r >= g) {
        g *= 2;
        k--;
    }
    if (k < 0) flag = false;
    while (g >= b) {
        b *= 2;
        k--;
    }
    if (k < 0) flag = false;
    cout << (flag ? "Yes" : "No") << endl;
}



Measured memory_bytes: 3628
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def resolve():
    N = int(input())
    ans = 0
    for i in range(1, N+1, 2):
        tmp = make_divisors(i)
        if len(tmp) == 8:
            ans += 1
    print(ans)
    return

resolve()

Measured memory_bytes: 9116
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    ans = 0
    if n<10:
        ans = n
    else:
        keta = len(str(n))
        top = int(str(n)[0])
        down = int(str(n)[1:])
        if top == 1:
            if down == 10**(keta-1)-1:
                ans = 1+(keta-1)*9
            else:
                ans = (keta-1)*9
        else:
            if down == 10**(keta-1)-1:
                ans = top+(keta-1)*9
            else:
                ans = top-1+(keta-1)*9
    
    print(ans)

main()            


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

int main(){
  string s;
  cin >> s;
  string ans;
  if(s=="Sunny") ans = "Cloudy";
  if(s=="Cloudy") ans = "Rainy";
  if(s=="Rainy") ans = "Sunny";
  cout<< ans << endl;
}

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

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

	string s;
	cin >> s;
	int64_t sum = 0;
	for (char c : s) {
		sum += (c-'0');
	}
	cout << (sum%9 == 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
#define FOR(i, n) for (long long i = 0; i < (n); ++i)
#define pb push_back
#define int long long
#define debug(x) std::cout << #x << ": " << x << '\n';
typedef long long ll;
const int N = 2e5 + 10;
std::vector<int> a[N];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int h, w, n;
    std::cin >> h >> w >> n;
    FOR(i, n) {
    	int x, y;
    	std::cin >> x >> y;
    	--x; --y;
    	a[y].push_back(x);
    }
    FOR(i, w + 10) {
    	a[i].push_back(h);
    	std::sort(a[i].begin(), a[i].end());
    }
    int minAnsw = 1e9, curDown = 0;
    FOR(i, w) {
    	auto it = std::lower_bound(a[i].begin(), a[i].end(), curDown);
    	minAnsw = std::min(minAnsw, curDown + (*it - curDown));
    	curDown++;
    	auto it2 = std::lower_bound(a[i + 1].begin(), a[i + 1].end(), curDown);
    	while (it2 < a[i + 1].end() && *it2 == curDown) {
    		curDown++;
    		++it2;
    	}
    	if (curDown >= h) {
    		break;
    	}
    }
    std::cout << minAnsw;
}

Measured memory_bytes: 14208
#include <iostream>
#include <map>
#include <cassert>
#include <cstdio>
using namespace std;

class Parser{
public:
  int i;
  string S;
  map<char,int> M;
  const string op = "+-*";
  long long parse(){
    i = 0;
    long long ret = expr(-1);
    return ret;
  }
  long long expr(int p){
    long long ret;
    if(isdigit(S[i])) ret = number();
    else{
      ++i; ret = expr(-1); ++i;
    }
    if(i == S.length() || op.find(S[i]) >= S.length())
      return ret;
    while(i < S.length() && op.find(S[i]) < S.length() && M[S[i]] > p){
      long long x;
      char o;
      o = S[i];
      ++i;
      x = expr(M[o]);
      if(o == '+') ret += x;
      if(o == '-') ret -= x;
      if(o == '*') ret *= x;
    }
    return ret;
  }
  long long number(){
    long long ret = 0;
    while(i < S.length() && isdigit(S[i])){
      ret *= 10LL;
      ret += (long long)(S[i] - '0');
      ++i;
    }
    return ret;
  }
};

int main(){
  string S;
  cin >> S;
  long long ans = -(1LL<<62) - (1LL<<62);
  Parser P;
  P.S = S;
  for(int i = 0; i < 3; ++i){
    for(int j = 0; j < 3; ++j){
      for(int k = 0; k < 3; ++k){
        P.M['+'] = i;
        P.M['-'] = j;
        P.M['*'] = k;
        ans = max(ans, P.parse());
      }
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3220
#include<stdio.h>
int tricheck(int x, int y, int z)
{
    static count=0;
    if(x+y>z && y+z>x && x+z>y){
        count++;
    }
    return count;
}
int main()
{
    int n, i, j, k, calc=0;
    scanf("%d", &n);
    int arr[n];
    for(i=0; i<n; i++){
        scanf("%d", &arr[i]);
    }
    for(i=0; i<n; i++){
        for(j=i+1; j<n; j++){
            if(arr[i]!=arr[j]){
                for(k=j+1; k<n; k++){
                    if(arr[k]!=arr[j] && arr[k]!=arr[i]){
                        calc=tricheck(arr[i], arr[j], arr[k]);
                    }
                }
            }
        }
    }
    printf("%d\n", calc);
    return 0;
}

Measured memory_bytes: 1736
from sys import stdin, stdout
from math import sqrt
from collections import defaultdict
#t = int(stdin.readline().strip())
#R, L, C, Vin = [float(x) for x in stdin.readline().strip().split()]
A, B = [int(x) for x in stdin.readline().strip().split()]
print("Yay!" if (A <= 8 and B <= 8) else ":(")

Measured memory_bytes: 3316
program main
    implicit none
    integer n, k, d
    integer, allocatable, dimension(:) :: a,p
    integer i,j,sum

    read(*,*) n, k
    allocate(p(n))
    do i = 1,n
        p(i) = 1
    end do

    do i = 1,k
        read(*,*) d
        allocate(a(d))
        read(*,*) a
        do j = 1, d
            p(a(j)) = 0
        end do
        deallocate(a)
    end do

    sum = 0
    do i = 1,n
        sum = sum + p(i)
    end do
    write(*,*) sum


end program

Measured memory_bytes: 2860
H, W = map(int, input().split())
N = int(input())
a = list(map(int, input().split()))
ans = [list([0] * W) for _ in range(H)]

color = 1
for i in range(H):
    for j in range(W):
        if a[color - 1] == 0:
            color += 1
        if i % 2 == 0:
            ans[i][j] = color
            a[color - 1] -= 1
        else:
            ans[i][-j - 1] = color
            a[color - 1] -= 1

for i in range(H):
    print(*ans[i])

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define FORE(i,a,b) for (int i=(int)(a);i<=(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REPE(i,n) FOR(i,0,n)
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define OUT(x) cout<<x<<endl;

typedef long long ll;
typedef pair<ll, ll> P;

int main() {
  int N; cin >> N;
  int upper[100000];
  int lower[100000];
  REP(i,100000) {
    upper[i] = 0;
    lower[i] = 0;
  }

  REP(i,N) {
    int v;cin >> v;
    if (i%2==0) upper[v-1]++;
    else lower[v-1]++;
  }
  vector<P> up;
  vector<P> low;
  REP(i,100000) {
    if (upper[i] > 0) up.push_back({upper[i],i});
    if (lower[i] > 0) low.push_back({lower[i],i});
  }

  auto sort_by_first = [](P a,P b) { return a.first > b.first; };

  sort(ALL(up),sort_by_first);
  sort(ALL(low),sort_by_first);

  up.push_back({0,-1});
  low.push_back({0,-1});

  int ans = N;
  if (up[0].second != low[0].second) {
    ans -= up[0].first+low[0].first;
  } else {
    ans -= max(up[0].first+low[1].first, up[1].first+low[0].first);
  }
  OUT(ans);

  return 0;
}

Measured memory_bytes: 2804
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)

const ll MOD = 1e9 + 7;

void solve(istream& cin, ostream& cout) {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  vector<vector<int>> dp(n + 1, vector<int>(k + 1));
  REP(i, n + 1) {
    dp[i][0] = 1;
  }
  REP(i, n) {
    cin >> a[i];
  }
  FOR(i, 1, n) {
    FOR(j, 1, k) {
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
      if (j - a[i - 1] - 1 >= 0) {
        dp[i][j] -= dp[i - 1][j - a[i - 1] - 1];
        dp[i][j] += MOD;
        dp[i][j] %= MOD;
      }
    }
  }
  cout << dp[n][k] << endl;
}

#ifndef TEST
int main() {
  solve(cin, cout);
}
#endif


Measured memory_bytes: 40192
#include <bits/stdc++.h>
#define rp(i,N) for(int i=0;i<N;i++)
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  vector<long long> count(N+1,0);
  rp(i,N){
    cin >> A.at(i);
  }
  rp(i,N){
    count.at(A.at(i))++;
  }
  long long sum;
  rp(i,N+1){
    sum+=count.at(i)*(count.at(i)-1)/2;
  }
  rp(i,N){
    cout << sum-count.at(A.at(i))+1 << endl;
  }
}

Measured memory_bytes: 4992
#include <stdio.h>
int main(void){
  char r[5],a[5];
  int i,j,h,b;
  while(1){
    scanf("%s %s",r,a);
    if(r[0]=='0'&&a[0]=='0')break;
    h=b=0;
    for(i=0;i<4;i++){
      if(r[i]==a[i])h++;
    }
    for(i=0;i<4;i++){
      for(j=0;j<4;j++){
	if(r[i]==a[j]&&i!=j)b++;
      }
    }
    printf("%d %d\n",h,b);
  }
  return 0;
}

Measured memory_bytes: 540
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define st string
#define ve(i) vector<i>
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define each(i, n) for(auto&& i: n)

int main() {
  st S, T;
  cin >> S >> T;
  cout << T << S << endl;
}  

Measured memory_bytes: 256