akhauriyash/Code-Regression huggingface dataset:
def s_sort(l):
    q = len(l)
    count = 0
    for i in range(q):
        minv = i
        for j in range(i+1, q):
            if l[j] < l[minv]:
                minv = j
        if minv != i:
            l[i], l[minv] = l[minv], l[i]
            count += 1
    print(' '.join(map(str, l)))
    print(count)


if __name__ == '__main__':
    N = int(input())
    ali = list(map(int, input().split()))
    s_sort(ali)



Measured memory_bytes: 5600
import java.util.Scanner;
class Main{
    public static void main(String[] av){
	Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
	int b=sc.nextInt();
	int c=sc.nextInt();
	int count=0;
	for(int i=a;i<=b;i++){
	    if(c%i==0) count++;
	}
	System.out.println(count);
	  

    
    
    }
}


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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...)
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    long long x;
    cin >> x;

    int ret = 0;
    long long y = 100;
    while (y < x) {
        ret++;
        y += y / 100;
    }

    cout << ret << "\n";

    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    for(int i = a; i <= b; i++) {
        if(a + k-1 >= i || b -k+1 <= i) cout << i << endl;
    }
}

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

int ans = 10000;
int h, w;
vector<vector<char>> s(60, vector<char>(60, '#'));
vector<vector<int>> a(60, vector<int>(60, 10000));
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

void search(int cnt, int x, int y){
	a[x][y] = cnt;
	if(h==x && w==y){
		ans = min(cnt,ans);
		return;
	}
	for(int dir = 0; dir < 4; ++dir){
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if(s[nx][ny] == '.' && cnt+1<a[nx][ny])
			search(cnt+1, nx, ny);
	}
}


int main(void){
	cin >> h >> w;
	int bk = 0;
	for(int i = 1; i <= h; ++i){
		for(int j = 1; j <= w; ++j){
			cin >> s[i][j];
			if(s[i][j] == '#') bk++;
		}
	}
	search(1,1,1);
	cout << (a[h][w]!=10000?h*w-bk-ans:-1) << endl;
	return 0;
}

Measured memory_bytes: 384
import sys
nums , money = map(int,input().split())

for i in range(nums+1):

    for x in range( nums +1 -i):

        if (i * 10000) + (x *5000) + ((nums -(i+x))*1000) == money:
            print(str(i) +" " + str(x) +" " +str((nums -(i +x))))
            sys.exit()

else:
    print("-1 -1 -1")

Measured memory_bytes: 3060
from collections import deque
INF = int(1e9) + 7
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))
if maze[0][0] == '#' or maze[h-1][w-1] == '#':
    print(-1)
    exit()


d = [[INF] * w for i in range(h)]
def bfs():
    #d = [[INF] * w for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([(0, 0)])
    d[0][0] = 0

    while len(que) != 0:
        val = que.popleft()
        if val[0] == h-1 and val[1] == w-1:
            break
        for i in range(4):
            nx = val[0] + dx[i]
            ny = val[1] + dy[i]
            if (0 <= nx < h and 0 <= ny < w and maze[nx][ny] != '#' and d[nx][ny] == INF):
                que.append((nx, ny))
                d[nx][ny] = d[val[0]][val[1]] + 1
    return d[h-1][w-1]
ans = bfs()
if ans == INF:
    print(-1)
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                cnt += 1
    print(cnt - (ans+1))

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

const ll mod = 1000000007;
const double eps = 1e-8;

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> cnt(N, 0);
    for (int i=0; i<K; ++i) {
        int d;
        cin >> d;
        for (int j=0; j<d; ++j) {
            int A;
            cin >> A;
            A--;
            cnt[A] ++;
        }
    }

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

    return 0;
}

Measured memory_bytes: 3624
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n,k,cnt=1; cin>>n>>k;
    string s; cin>>s;
    rep(i,n-1)if(s[i]!=s[i+1]) cnt++;
    cout<<(cnt>2*k ? n-(cnt-2*k) : n-1)<<endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <iomanip>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
const int inf = 1e9;
const ll linf = 1LL << 50;
int p[11];
int c[11];
int dp[11][1001];
int d, g;

bool calc(int x){
		for(int i = 0; i <= d; i++){
				for(int j = 0; j < x + 1; j++){
						dp[i][j] = 0;
				}
		}
		for(int i = 0; i < d; i++){
				dp[i + 1][0] = 0;
				for(int j = 1; j <= x; j++){
						dp[i + 1][j] = 0;
						for(int k = 0; k <= min(j, p[i]); k++){
								dp[i + 1][j] = max(dp[i + 1][j], dp[i][j-k] + k * (i + 1));
						}
						if(j >= p[i])dp[i + 1][j] = max(dp[i + 1][j], dp[i][j-p[i]] + p[i] * (i + 1) + c[i]);
						if(dp[i+1][j] >= g)return true;
				}
		}
		return false;
}

int main(int argc, char const* argv[])
{
	cin >> d >> g;
	g = g / 100;
	int sum = 0;
	for(int i = 0; i < d; i++){
			cin >> p[i] >> c[i];
			c[i] /= 100;
			sum += p[i];
	}
	int ld = 0, rd = sum;
	while(rd - ld > 1){
			int md = (rd + ld) / 2;
			if(calc(md))rd = md;
			else ld = md;
	}
	cout << rd << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
 int H,W;
 int i,j;
  while(1)
    {
      scanf("%d %d",&H,&W);
      if (H == 0 && W == 0)break;

      for(j = 0;j < H; j++)
        {
      for(i = 0;i < W; i++)
        {
          printf("#");
        }
      printf("\n");
        }
      printf("\n");
    }
  return 0;
}

Measured memory_bytes: 572
import sys

def cross_product(a, b):
    ax, ay = a
    bx, by = b
    return ax * by - ay * bx


def sub(a, b):
    a1, a2 = a
    b1, b2 = b
    return b1 - a1, b2 - a2


def judge(p1, p2, p3, pp):

    cnt = 0
    for a, b in ((p1, p2), (p2, p3), (p3, p1)):
        vec1 = sub(a, b)
        vec2 = sub(a, pp)
        if cross_product(vec2, vec1) > 0:
            cnt += 1
    if cnt == 0 or cnt == 3:
        print("YES")
    else:
        print("NO")


if __name__ == '__main__':
    for line in sys.stdin:
        inputs = [float(s) for s in line.split()]
        p1 = (inputs.pop(0), inputs.pop(0))
        p2 = (inputs.pop(0), inputs.pop(0))
        p3 = (inputs.pop(0), inputs.pop(0))
        pp = (inputs.pop(0), inputs.pop(0))
        judge(p1, p2, p3, pp)


Measured memory_bytes: 5592
N = int(raw_input())
A = map(int, raw_input().split())

def solve(N, A):
    if N == 1: return True
    x = A.pop()
    heads = [x, x-1]
    while A:
        x = A.pop()
        possible = []
        for y in (x, x-1):
            if any(y <= z for z in heads):
                possible.append(y)
        heads = possible
        if not heads: return False
    return bool(heads)

print 'Yes' if solve(N, A) else 'No'


Measured memory_bytes: 42348
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
//const ll MOD = 1e9 + 7;
const ll MOD = 998244353;


int main() {
	string s;
	cin >> s;

	ll sum = 0;
	for (int i = 0; i < s.length(); i++) {
		sum += (s[i] - '0');

	}

	if (sum % 9 == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 3700
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
k=0
s=float('inf')
for i in range(n):
    if abs(t-h[i]*.006-a)<s:
        s=abs(t-h[i]*.006-a)
        k=i
print(k+1)

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

int main() {
    int n, m;
    cin >> n >> m;
    int a[n][m] = {};
    int b[m] = {};
    int x;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> x;
            a[i][j] = x;
        }
    }
    for (int i = 0; i < m; i++){
        cin >> x;
        b[i] = x;
    }
    
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            sum += a[i][j] * b[j];
        }
        cout << sum << endl;
    }
}


Measured memory_bytes: 3136
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
G = {k: [] for k in range(N)}
for _ in range(M):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a-1].append(b-1)
    G[b-1].append(a-1)

visited = [False]*N
visited[0] = True


def dfs(v):
    if all(visited):
        return 1
    r = 0
    for nv in G[v]:
        if visited[nv] is False:
            visited[nv] = True
            r += dfs(nv)
            visited[nv] = False
    return r


print(dfs(0))


Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;

class C
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var qs = new int[n].Select(_ => Console.ReadLine().Split());

		var l = new LinkedList<int>();

		foreach (var q in qs)
		{
			switch (q[0])
			{
				case "insert":
					l.AddFirst(int.Parse(q[1]));
					break;
				case "delete":
					l.Remove(int.Parse(q[1]));
					break;
				case "deleteFirst":
					l.RemoveFirst();
					break;
				case "deleteLast":
					l.RemoveLast();
					break;
				default:
					break;
			}
		}
		Console.WriteLine(string.Join(" ", l));
	}
}



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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<string> d(m);
    for (int i=0;i<m;++i) cin >> d[i];
    int sum=0;
    for (int i=0;i<m;++i)
        for (int j=0;j<n;++j)
            sum+=(d[i][j]=='W');
    int ans=0,Min=sum;
    for (int j=0;j<n;++j){
        for (int i=0;i<m;++i)
            sum+=(d[i][j]=='E'?1:-1);
        if (sum<Min) Min=sum,ans=j+1;
    }
    cout << ans << ' ' << ans+1 << '\n';
}


Measured memory_bytes: 4260
R, G, B, N = map(int, input().split())

def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

ans = 0

for i in range(N + 1):
    for j in range(N + 1):
        t = (N - G * i - B * j)
        if is_integer_num(t / R) and t >= 0:
            ans += 1

print(ans)


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

using namespace std;

#define int long long
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll N=1e5+10,M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
const int INF=1e9+7;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}

#define trace(...) cerr<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    const char *comma=strchr(names+1,',');
    cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
    __f(comma+1,args...);
}

int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}

int n,m,k;
int a[N],b[N],c[N],d[N];


int cnt[N];
int fri[N];

struct dsu
{
    static const int MAX_N=100005; //nodes
    int parent[MAX_N];
    int size[MAX_N];

    void make_sets(){
        for(int i=0;i<MAX_N;i++){
            parent[i]=i;
            size[i]=1;
        }
    }

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

    void make_union(int u,int v){
        u=find_set(u);
        v=find_set(v);
        if(u==v) return;
        if(size[u]<size[v]) swap(u,v);
        parent[v]=u;
        size[u]+=size[v];
    }

    bool same_set(int u,int v){
        return find_set(u)==find_set(v);
    }
};

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    dsu p;
    p.make_sets();
    rep(i,1,m+1){
        cin >> a[i] >> b[i];
        fri[a[i]]++;fri[b[i]]++;
        p.make_union(a[i],b[i]);
    }
    rep(i,1,k+1){
        cin >> c[i] >> d[i];
        if(p.find_set(c[i])==p.find_set(d[i])) cnt[c[i]]++,cnt[d[i]]++;
    }
    rep(i,1,n+1){
        int x=p.find_set(i);
        cout << p.size[x]-cnt[i]-fri[i]-1 << " ";
    }
    return 0;
}

Measured memory_bytes: 7040
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int n,in,c,mi=0,pl2=0;
    long long int sub=0;
    vector<int> a,b;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>in;
        a.push_back(in);
    }
    for(int i=0;i<n;i++){
        cin>>in;
        b.push_back(in);
    }
    for(int i=0;i<n;i++){
        c=b[i]-a[i];
        sub+=c;
        if(c<=0){
            mi+=-c;
        }
        else{
            pl2+=c/2;
            pl2+=c%2;
        }
    }
    if(sub<mi||sub<pl2){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
    }
}

Measured memory_bytes: 384
/*Made by Shivam Solanki*/
#include<bits/stdc++.h>
using namespace std;
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define ll long long int
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<pii> vp;
typedef vector<pll> vpll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef set<int> sii;
typedef set<ll> sll;
typedef unordered_map<int,int> umii;
typedef unordered_map<ll,ll> umll;
#define rep(i,k,n) for (int i = k; i < n; ++i) 
#define repr(i,k,n) for (int i = n; i>=k; --i)
#define REP(i,k,n) for (int i = k; i <= n; ++i) 
#define REPR(i,k,n) for (int i = k; i >= n; --i)
#define repll(i,k,n) for (ll i = k; i < n; ++i) 
#define pb push_back
#define mp make_pair
#define __gcd gcd
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int INF = 1e9+5;
const int MOD = 1e9+7;

void solve(){
    int n;
    cin>>n;
    vi a(n);
    rep(i,0,n){
        cin>>a[i];
    }
    set<pair<int,int>>s;
    int sum=0;
    rep(i,0,n-1){
        rep(j,i+1,n){
            if(s.count({i,j})==0 or s.count({j,i})==0){
                sum+=a[i]*a[j];
                s.insert({i,j});
                s.insert({j,i});
            }
        }
    }
    cout<<sum;
}

int main(){
    // #ifndef ONLINE_JUDGE  
        // freopen("input.txt", "r", stdin); 
        // freopen("output.txt", "w", stdout); 
    // #endif 
    // fastio;
    int t=1;
    // cin>>t;
    while(t--)
        solve();
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <tuple>
#include <cassert>

using namespace std;

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

typedef long long ll;
long long int gcd(long long int x,long long int y){
    long long int r;
    if(x == 0 || y == 0)  return 0;

    while((r = x % y) != 0) 
    {
         x = y;
        y = r;
    }
    return y;
}

int main(){
    long long int n,m;
    string s,t; cin >> n >> m >> s >> t;
    if(n==m){
        if(s == t) cout << n << endl;
        else cout << -1 << endl;
        return 0;
    }
    if(n<m){swap(s,t); swap(n,m);}
    ll lcm = (n * m) / gcd(n,m);
    ll gc  = gcd(n,m);
    rep(i,gc){
        if(s[(n / gc) * i] != t[(m / gc) * i]){
            cout << -1 << endl;
            return 0;
        }
    }
    
    if(s[0] == t[0]){ cout << lcm << endl;}
    else cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using u128 = __uint128_t;

#define int long long
#define idxSet tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define atIdx find_by_order
#define idxOf order_of_key
#define MOD 1000000007
#define MAX 200005
#define endl '\n'

#define v(type) vector<type>
#define p(type1, type2) pair<type1 , type2>
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int dp[MAX];

void solve() {
    int k;
    cin>>k;
    queue<int> q;
    for(int i = 1 ; i < 10 ; i++){
        q.push(i);
    }
    int last = 0;
    for(int i = 0 ; i < k ; i++){
        last = q.front();
        q.pop();
        if(last % 10 != 0){
            q.push(last * 10 + (last % 10) -1);
        }
        q.push(last * 10 + (last % 10));
        if(last % 10 != 9){
            q.push(last * 10 + (last % 10 ) + 1);
        }
    }
    cout<<last<<endl;

}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin>>t;
    while (t--)
        solve();
    return 0;
}

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

int main(){
while(1){
	int n,m;
	vector<int> p,q;
	scanf("%d%d",&n,&m);
if(n==0&&m==0)break;
	q.push_back(0);
	for(int i=0;i<n;i++){
		int a;
		scanf("%d",&a);
		p.push_back(a);
		q.push_back(a);
	}
	for(int i=0;i<n;i++){
		for(int j=i;j<n;j++){
			q.push_back(p[i]+p[j]);
		}
	}
	sort(q.begin(),q.end());
	int ans=0;
	int f=0,s=q.size()-1;
	while(1){
		if(q[f]+q[s]>ans&&q[f]+q[s]<=m)ans=q[f]+q[s];
		if(q[f]+q[s]<=m)f++;
		if(q[f]+q[s]>m)s--;
		if(f>s)break;
	}
	printf("%d\n",ans);
}
}

Measured memory_bytes: 5008
n = int(input())
s = input()

dp = [[0]*(n+1) for _ in range(n+1)]

for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1]+1


ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        x = min(dp[i][j], j-i)
        if ans < x:
            ans = x
print(ans)


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

using namespace std;

#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define v(d_type) vector<d_type>
#define p(d_type1, d_type2) pair<d_type1, d_type2>
#define F first
#define S second
#define loop(i, s, n) for(int i = s; i < n; i++)
#define print_vec(X) loop(i, 0, X.size()) cout << X[i] << "\n"
#define nl "\n"
#define fat 1000000007

int main()
{
    boost;

    int n, ans = 0;
    cin >> n;

    v(int) a(n), b(n), c(n - 1);
    loop(i, 0, n)   cin >> a[i];
    loop(i, 0, n)   cin >> b[i];
    loop(i, 0, n - 1)   cin >> c[i];

    int sum = 0;
    sum = accumulate(b.begin(), b.end(), sum);

    ans += sum;

    loop(i, 0, n - 1)
        if(a[i + 1] - 1 == a[i] && a[i] != n) ans += c[a[i] - 1];

    cout << ans << nl;
    return 0;

}

Measured memory_bytes: 256
d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
t = [int(input()) for _ in range(d)]
MAX = 26

last = [0] * MAX

score = 0
for day, e in enumerate(t, 1):
    score += s[day-1][e-1]
    last[e-1] = day

    for ec, elast in zip(c, last):
        score -= ec * (day - elast)

    print(score)




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

using namespace std;

typedef long long ll;

int main(){
	int t[5];
	int m = 10;
	for(int i = 0; i < 5; i++){
		cin >> t[i];
		if(t[i]%10)m = min(t[i]%10, m);
	}
	int ans = 0;
	for(int i = 0; i < 5; i++)ans += (t[i]+9)/10*10;
	m = 10-m;
	cout << ans-m << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
using namespace std;
int main() {
	int N;
	cin >> N;
	int Z = N % 2;
	if (Z == 0) {
		int X = N / 2;
		cout << X;
	}
	else {
		int X = (N + 1) / 2;
		cout << X;
	}
}

Measured memory_bytes: 256
N = int(input())
liste = input().split()
number = [int(x) for x in liste]
total = 1
i = 0
if 0 in number:
    total = 0
else:
    while i < N:
            total *= number[i]
            i = i + 1
            if total > 10**18:
                total = -1
                break
print(total)

Measured memory_bytes: 21480
#include <bits/stdc++.h>
#define inf 2e18
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
vector<int>v;
set<int>s;
int a[2*100005];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll a,b,k;
    cin>>a>>b>>k;
    ll d=min(a,k);
    k=k-d;
    cout<<a-d<<" "<<b-min(b,k)<<endl;
}



Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m, k = map(int, input().split())
uf = UnionFind(n+1)
n_rlts = [0]*(n+1)
for i in range(m):
    a,b = map(int, input().split())
    n_rlts[a] += 1
    n_rlts[b] += 1
    uf.union(a,b)
for i in range(k):
    c,d = map(int, input().split())
    if uf.same(c,d):
        n_rlts[c] += 1
        n_rlts[d] += 1
res = ""
for i in range(1,n+1):
    res += str(uf.size(i)-1-n_rlts[i]) + " "
print(res[:-1])

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

using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.in" , "r" , stdin);
#endif
    int n;
    cin >> n;

    int mn = 1e9 , ans = 0;
    for (int i = 0 ;i < n ;i++) {
        int x;
        cin >> x;
        ans += x < mn;
        mn = min(mn , x);
    }

    cout << ans;
}

Measured memory_bytes: 3696
#include <stdio.h>
 
int main(){
  int a,b,sum;
  char op;
 
  while(1){
    if(op=='?') break;
    scanf("%d %c %d",&a,&op,&b);
 
    if(op=='+') sum = a+b;
    else if(op=='-') sum = a-b;
    else if(op=='*') sum = a*b;
    else if(op=='/') sum = a/b;
    else return 0;
    printf("%d\n",sum);
  }
  return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector <int> vec(N);
  for (int i = 0; i < N; i++){
  cin >> vec.at(i);
  }
  int count = 0;
  for (int i = 0; i < N; i++){
  if(vec.at(i) <= K - vec.at(i)){
  count += vec.at(i);
  }else{
  count += K - vec.at(i);
  }
  }
  cout << 2*count;
}


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

#define reps(v, f, l) for (int v = (f), v##_ = (l); v < v##_; ++v)
#define rep(v, n) reps(v, 0, n)
#define lep(v, n) reps(v, 1, n + 1)

using namespace std;

typedef long long int lint;

static inline int in(){ int x; scanf("%d", &x); return x; }
static inline lint inl(){ lint x; scanf("%lld", &x); return x; }
template<typename T> void show(T& a, char del='\n', char last='\n'){ rep(i, a.size() - 1) cout << a[i] << del; cout << a[a.size() - 1] << last; }

int main()
{
  int n;
  while (n = in()){
    vector<pair<int, int> > islands;
    rep(i, n){
      int item;
      int lim;
      item = in();
      lim = in();
      islands.push_back(make_pair(lim, item));
    }
    sort(islands.begin(), islands.end());
    int total = 0;
    bool ok = true;
    rep(i, n){
      if (total > islands[i].first){
        ok = false;
        break;
      }
      total += islands[i].second;
      if (total > islands[i].first){
        ok = false;
        break;
      }
    }
    puts(ok ? "Yes" : "No");
  }
  return 0;
}

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

int main() {
	int x;
	cin >> x;
	int sum = 0;
	int n = x;
	while (x > 0) {
		sum += x % 10;
		x /= 10;
	}
	if (n % sum == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

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

signed main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int n, l; cin >> n >> l;
  int a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
  int m = 0;
  for (int i = 0; i < n - 1; i++) m = max(m, a[i] + a[i + 1]);
  if (m < l) cout << "Impossible" << "\n";
  else {
    cout << "Possible" << "\n";
    int j;
    for (int i = 0; i < n; i++) {
      if (m == a[i] + a[i + 1]) {
        j = i;
        break;
      }
    }
    for (int i = n - 1; i > j + 1; i--) cout << i << "\n";
    for (int i = 1; i <= j + 1; i++) cout << i << "\n";
  }
  return 0;
}

Measured memory_bytes: 1280
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>

using namespace std;
using ll = long long;

// inf
const ll infl = 1LL << 60;
const int inf = 1 << 30;

// コピペごめんなさい！
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N + 1) { //最初は全てが根であるとして初期化
        for(int i = 0; i <= N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int groupNum() {
        set<int> ap;
        for (int i = 1; i < par.size(); ++i) {
            ap.insert(root(i));
        }
        return ap.size();
    }
};

int main() {
    int N, M; cin >> N >> M;
    UnionFind uf(N);

    for (int i = 0; i < M; ++i) {
        int x, y, z; cin >> x >> y >> z;

        uf.unite(x, y);
    }

    cout << uf.groupNum() << endl;
    return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

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

    int lmax=0, lid;
    for(int i=0; i<n-1; i++){
        if(lmax < a[i] + a[i+1]){
            lmax = a[i] + a[i+1];
            lid = i + 1;
        }
    }

    if(lmax < l){
        cout << "Impossible" << endl;
    }
    else{
        cout << "Possible" << endl;
        for(int i=1; i<lid; i++){
            cout << i << endl;
        }
        for(int i=n-1; i>lid; i--){
            cout << i << endl;
        }
        cout << lid << endl;
    }
}

Measured memory_bytes: 1152
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <cstring>
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <numeric>
#include <float.h>
#include <math.h>
#include <sstream>
#include <iterator>
using namespace std;
// repマクロの定義
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// allマクロの定義
#define all(v) v.begin(), v.end()
const  long long INF = 1LL << 60;
typedef  long long ll;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}



int ctoi(char c) {
 	switch (c) {
		case '0': return 0;
		case '1': return 1;
		case '2': return 2;
		case '3': return 3;
		case '4': return 4;
		case '5': return 5;
		case '6': return 6;
		case '7': return 7;
		case '8': return 8;
		case '9': return 9;
		default: return 0;
	}
}

bool is_prime(const unsigned n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: // fall-through
        case 3: return true;
    } // n > 3 が保証された

    if(n % 2 == 0 || n % 3 == 0) return false;
    // n は 2 と 3 のいずれの倍数でもないことが保証された
    // これより n は (6の倍数)-1 か (6の倍数)+1 である

    // 6の倍数前後の数を使って試し割りをする
    for(unsigned i = 5; i * i <= n; i += 6) {
        if(n % i     == 0) return false; // (6の倍数)-1
        if(n % (i+2) == 0) return false; // (6の倍数)+1
    }

    return true;
}

map<ll,ll> mp;

auto findFactors(ll num){
	
    ll i;
    while (num % 2 == 0){ // 偶数の素数は2のみ
        if(mp.count(2)){
			mp[2] = mp[2] + 1;
		}
		else{
			mp[2] = 1;
		}
        num /= 2;
    }
    for (i = 3; i <= num; i++){ // 他の素数で割っていく
        while (num % i == 0){
			if(mp.count(i)){
			mp[i] = mp[i] + 1;
		}
		else{
			mp[i] = 1;
		}
            num /= i;
        }
    }
    return 0;
}
ll kaizyou(ll n){
    if(n == 1){
        return 1;
    }
    else{
        return (n * kaizyou(n-1)) % 1000000007;
    }
}



int main(){
int N; cin >> N;
vector<ll> A(N);
vector<ll> B(N);
ll s = 0,t = 0;
ll cnt = 0;
ll sum = 0;
priority_queue<ll> pq;
rep(i,N) {
    cin >> A[i];
    s += A[i];
}
rep(i,N) {
    cin >> B[i];
    t += B[i];
    if(B[i] > A[i]){
        cnt++;
        sum += B[i] - A[i];
    }
    else if(B[i] < A[i]){
        pq.push(A[i] - B[i]);
    }
}
if(s < t){
    cout << -1 << endl;
}
else if(cnt == 0){
    cout << 0 << endl;
}
else{
    while(sum > 0){
        sum -= pq.top();
        pq.pop();
        cnt++;
    }
    cout << cnt << endl;
}
}

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

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef long double LD;
typedef pair<LD, LD> PLDLD;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()

const int N=101;
vector<vector<LL>> com(N,vector<LL>(N));
LL comb(LL p, LL q)
{

    //cout<<p-q<<" "<<q<<endl;
    return com[p-q][q];
}

int main()
{
    com[0][0]=1;
    REP(i,N-1)
    REP(j,i+1)
    {
        com[j+1][i-j]+=com[j][i-j];
        com[j][i-j+1]+=com[j][i-j];
    }

    int n,a,b;
    cin>>n>>a>>b;
    vector<LL> v(n);
    REP(i,n)
        cin>>v[i];

    sort(ALL(v),greater<LL>());
    double aver=0;
    REP(i,a)
    aver+=v[i];
    aver/=a;
    cout<<setprecision(8)<<fixed<<aver<<endl;
    LL m=v[a-1],c=0, d=0;
    REP(i,n)
        if(m==v[i])c++;
        else if(m<v[i])d++;

    //cout<<c<<" "<<d<<endl;
    LL ans=0;
    if(d>0)
    {
        ans+=comb(c,a-d);
    }
    else
    {
        FOR(i,a,b+1)
        {
            if(i>c+d) continue;
            ans+=comb(c,i-d);
        }
    }

    cout<<ans<<endl;

}



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

using vll = std::vector<long long>;
constexpr long long mod{1000000007};

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	std::vector<vll> combi(n + 1, vll(k + 1));
	combi[0][0] = 1;
	for (int n_i{1}; n_i <= n; n_i++)
	{
		int a;
		scanf("%d", &a);
		long long sum{};
		for (int k_i{}; k_i <= k; k_i++)
		{
			sum += combi[n_i - 1][k_i];
			sum %= mod;
			if (k_i - a - 1 >= 0)
			{
				sum += mod - combi[n_i - 1][k_i - a - 1];
				sum %= mod;
			}
			combi[n_i][k_i] = sum;
		}
	}
	printf("%lld\n", combi[n][k]);

	return 0;
}

Measured memory_bytes: 80256
#include<iostream>
#include<math.h>
using namespace std;

#define ll long long
int main(){


int n;

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

ll floormid, ceilmid;
ceilmid=ceil(sum/n);
floormid= floor(sum/n);


ll ans1=0, ans2=0;
for(int i=0;i<n;i++)
{   
ans1+= pow(arr[i]-ceilmid,2);
ans2+= pow(arr[i]-floormid,2);

}

cout<<min(ans1, ans2);
  
}

Measured memory_bytes: 3208
#include <cstdio>
#include <cstring>
#include <utility>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
using namespace std;


int main(){
  int n; cin >> n;
  long long int a[100001]={};
  long long int sum[100001]={};
  bool ok[100001];
  ok[n-1]=true;
  int i;

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

  for(i=0;i<n;i++){
    if(i==0)
      sum[i] = a[i];
    else
      sum[i] = sum[i-1] + a[i];
  }

  for(i=0;i<n-1;i++)
    if(sum[i] * 2 >= a[i+1])
      ok[i] = true;

  int ans = 1;
  for(i=n-2;i>=0;i--){
    if(ok[i])
      ans++;
    else
      break;
  }

  cout << ans << endl;

  return 0;
}


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

int main(){
  int N; cin >> N;
  vector<int> B(N+1);
  for(int i=1;i<N;i++){
    cin >> B[i];
  }
  B[0]=B[1];
  B[N]=B[N-1];
  int ans=0;
  for(int i=N;i>0;i--){
    ans+=min(B[i],B[i-1]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <iostream>
#include<cstdio>
#include <cmath>
#define endl '\n'
using namespace std;
int box[102];
int main()
{
	int n,m,x;
	cin>>n>>m>>x;
	for(int i = 1; i<=m; i++)
	{
		int p;
		cin>>p;
		box[p] = 1;
	}
	int tollR = 0,tollL = 0,posR = x,posL = x;
    while(posR!=n){
			if(box[posR+1]==1)tollR++,posR++;
			else if(!box[posR+1])posR++;
    }
    while(posL!=0){
        if(box[posL-1]==1)tollL++,posL--;
        else if(!box[posL-1])posL--;
    }
	cout<<min(tollR,tollL)<<endl;	
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<int,int> Pair;
const int Nmax = 1e5 + 5, Mod = 1e9 + 7;

int ans = 1, answer = 1, n, i, x;

int main()
{
  //  freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<=n; ++i)
    {
        cin >> x;
        if(x % 2 == 0) ans *= 2;
        answer *= 3;
    }

    cout << answer - ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

bool distance(int point1[], int point2[], int d){
	int temp = 0;
	for(int i = 0; i<d; i++){
		temp += pow(point1[i] - point2[i], 2);
	}
	int k = sqrt(temp);
	if(k*k == temp){
		return true;
	}
	else{
		return false;
	}
}

int main() {
	int n, d, count = 0;
	cin >> n >> d;
	int coor[n][d];
	for(int i = 0; i<n; i++){
		for(int j = 0; j<d; j++){
			cin >> coor[i][j];
		}
	}

	for(int i = 0; i<n; i++){
		for(int j = i+1; j<n; j++){
			if(distance(coor[i], coor[j], d)){
				count++;
			}
		}
	}

	cout << count << endl;
}

Measured memory_bytes: 256
/*     ####   ####  #               ####  #        ##   #    # #    # ###### #####
      #      #    # #              #      #       #  #  ##  ## ##  ## #      #    #
       ####  #    # #               ####  #      #    # # ## # # ## # #####  #    #
           # #  # # #                   # #      ###### #    # #    # #      #####
      #    # #   #  #              #    # #      #    # #    # #    # #      #   #
       ####   ### # ###### #######  ####  ###### #    # #    # #    # ###### #    #
*/
 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long  LLi;
typedef long long LL;
typedef vector<long long> VLL;
typedef vector<string> VS;
typedef vector<pair<LLi, LLi> > VP;
 
 
#define For(in) for (LLi i = 0; i < (n); i++)
#define FOR(in) for(LLi i=1; i <= (n); i++)
#define pb push_back
#define sr(v) sort(v.begin(), v.end())
#define rev(v) reverse(v.begin(), v.end())
#define uniq(v) v.erase(unique(v.begin(), v.end()), v.end());
#define exit(); return 0;
#define no "NO"
#define yes "YES"
#define con continue;
 

 
 
int main()
{
	long long n,m;
	cin>>n>>m;
	vector<string> v;
	for(int i=0; i<n; i++)
	{
		string s;
		cin>>s;
		v.pb(s);
	}
	sr(v);
	for(int i=0; i<n; i++)cout<<v[i];
	cout<<endl;
   
 
    exit()
 
 
}


Measured memory_bytes: 3604
import java.util.*
import java.math.*
import java.lang.Math.*

private val readString: ()->String = {readLine()!!}
private val readInt: ()->Int = { readLine()!!.toInt() }
private val readLong: ()->Long = { readLine()!!.toLong() }
private val readListInt: ()->List<Int> = { readLine()!!.split(' ').map(String::toInt) }
private val readListLong: ()->List<Long> = { readLine()!!.split(' ').map(String::toLong) }
private val errPrintln: (String)->Unit = { msg -> System.err.println(msg) }
private val MOD = 1e9.toLong()+7


fun greedyBitFS(item: List<Pair<Int, Int>>, bonus: List<Int>, LowLimit: Int): Int {
    val N = item.size
    var res = Int.MAX_VALUE;
    for (p in 0 until (0b01 shl N)) {
        var ptn = p
        var scr = 0
        var cnt = 0
        var lv = -1
        for(i in 0 until N) {
            val vi = item[i].first
            val ci = item[i].second
            if ((ptn and 0b01) == 1) {
                scr += vi * ci + bonus[i]
                cnt += ci;
                if (scr >= LowLimit) {
                    res = min(res, cnt)
                }
            } else {
                lv = max(lv, i)
            }
            ptn = ptn shr 1
        }
        if (scr < LowLimit) {
            if (lv >= 0) {
                val v = item[lv].first
                val c = item[lv].second
                for(j in c-1 downTo  1) {
                    if (scr + v * j >= LowLimit) {
                        res = min(res, cnt + j)
                    }
                }
            }
        }
    }
    return res
}


fun main(args: Array<String>) {
    val (D,G) = readListInt()
    val item = Array<Pair<Int, Int>>(D){ Pair(0,0) }
    val C = Array<Int>(D){0}

    for(i in 0 until D) {
        val pc = readListInt()
        item[i] = Pair(100*(i+1), pc[0])
        C[i] = pc[1]
    }

    val ans = greedyBitFS(item.toList(), C.toList(), G)

    println(ans)
}


Measured memory_bytes: 36540
n,k=[int(x) for x in input().rstrip().split()]
r,s,p=[int(x) for x in input().rstrip().split()]
t=input()
dp=["" for x in range(n)]
ans=0
for i in range(k):
  if t[i]=="r":
    ans+=p
    dp[i]="p"
  elif t[i]=="p":
    ans+=s
    dp[i]="s"
  else:
    ans+=r
    dp[i]="r"


for i in range(k,n):
  if t[i]=="r":
    if dp[i-k]!="p":
      ans+=p
      dp[i]="p"
  elif t[i]=="p":
    if dp[i-k]!="s":
      dp[i]="s"
      ans+=s
  else:
    if dp[i-k]!="r":
      dp[i]="r"
      ans+=r
print(ans)


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

int shape(int h, int w);

int shape(int h, int w)
{
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cout << "#";
        }
        cout << endl;
    }
    cout << endl;
}

int main()
{
    int n = 10000;
    int array[n][2];
    int cnt;
    for (int i = 0; i < n; i++)
    {
        cin >> array[i][0] >> array[i][1];
        if (array[i][0] == 0 && array[i][1] == 0)
        {
            cnt = i;
            break;
        }
    }
    for (int i = 0; i < cnt; i++)
    {
        shape(array[i][0],array[i][1]);
    }
}


Measured memory_bytes: 3092
def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table

N=int(input())
print(sum(num_divisors_table(N-1)))

Measured memory_bytes: 16652
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rng(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;


int main() {
  int n;
  cin >> n;
  cout << (n>=30? "Yes":"No") << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <iostream>

int main()
{
    int W, H, x, y;
    scanf("%d %d %d %d", &W, &H, &x, &y);
    printf("%f ", (double) 1.0 * W * H / 2);
    if(W%2==0 && H%2==0 && W/2==x && H/2==y) printf("%d\n", 1);
    else printf("%d\n", 0);
}

Measured memory_bytes: 256
import math

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

nn = int(input())
aa = list(map(int,input().split()))

ne = [0]*(nn+1)
cn = [0]*(nn+1)
cnminus1 = [0]*(nn+1)
#print(nn,aa)
#print(len(ne))
for i in range(nn):
    ne[aa[i]] += 1

for i in range(nn+1):
 #   print(ne[i])
    if ne[i] == 0:
        cn[i] = 0
        cnminus1[i] = 0
    elif ne[i] == 1:
        cn[i] = 0
        cnminus1[i] = 0
    elif ne[i] == 2:
        cn[i] = 1
        cnminus1[i] = 0
    else:
        cn[i] = combinations_count(ne[i],2)
        cnminus1[i] = combinations_count(ne[i]-1,2)

sum_cn = sum(cn)

for i in range(nn):
    print(sum_cn - cn[aa[i]] + cnminus1[aa[i]])



Measured memory_bytes: 158360
class BIT:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

N = int(input())
p = list(map(lambda x: int(x)-1, input().split()))
a = BIT(N)
b = BIT(N)
a.add(0, 1)
b.add(0, N)
for i in range(1, N):
    a.add(i, 1)
    b.add(i, -1)
for i, j in enumerate(p):
    a.add(j, i)
    b.add(0, i)
    b.add(j+1, -i)
print(*[a.sum(i) for i in range(N)])
print(*[b.sum(i) for i in range(N)])

Measured memory_bytes: 48900
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define chmin(a,b) if((a)>(b)) (a)=(b);
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={1,0,-1,0,1,-1,-1,1};
int dy[]={0,1,0,-1,1,1,-1,-1};
const int MOD = 1e9+7;
const int INF = 1e18+10;

/*--------------------------------------------------------------------*/


signed main(){
  int a; cin>>a;
  cout<<a+a*a+a*a*a<<endl;

  return 0;
}


Measured memory_bytes: 3640
#include <iostream>


int main(){
int a[3];
int d;
std::cin >> a[0] >> a[1] >> a[2];
for(int i=3;i>0;i--){
 for(int j=0;j<i-1;j++){
    if (a[j]>a[j+1]){
     d = a[j];
     a[j] = a[j+1];
     a[j+1] = d;
  }
 }
}
std::cout << a[0] << " " << a[1] << " " << a[2] <<"\n";

return 0;

}

Measured memory_bytes: 3092
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define DEBUG2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl
typedef long long ll;
class Solver{
public:
    static const int MAXN=1e5+10;
    int N,M;
    int re[MAXN];
    void solve(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>N>>M;
        int ml=1e9;
        for(int u=0;u<M;u++){
            int a,b;
            cin>>a>>b;
            ml=min(ml,a);
            if(re[a]==0||re[a]>b)re[a]=b;
        }
        int lb=re[ml],ans=1;
        for(int u=1;u<=N;u++){
            if(re[u]==0)continue;
            if(u>=lb){
                ans++;
                lb=re[u];
            }
            else if(lb>re[u])lb=re[u];
        }
        cout<<ans;
    }
};
int main()
{
    // freopen("in.txt","r",stdin);
    (new Solver())->solve();
}

Measured memory_bytes: 640
n=int(input())
abc=[[-1,-1,-1,-1]]

for i in range(n):
  a,b,c=map(int,input().split())
  abc.append([-1,a,b,c])
dp=[[0 for i in range(4)] for j in range(n+1)]

for i in range(1,n+1):
  for j in range(1,4):
    for k in range(1,4):
      if j==k:
        continue
      dp[i][k]=max(dp[i][k],dp[i-1][j]+abc[i][k])
ans=max(dp[n])
print(ans)

Measured memory_bytes: 48624