akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9

int N, M;
vector<int> a, b;

int main(){
  string s;
  cin >> s;
  int c = s.size()-2;
  cout << s[0] << c << s.back() << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

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



int main(){
    int n;
    cin >> n;
    string s;
    string t;
    cin >> s >> t;
    vector<int> a[26];
    rep(i,n){
        a[s[i]-'a'].push_back(i);
    }
    if(s[0]!=t[0]){
        cout << -1 << endl;
        return 0;
    }
    int id = 0;
    for(int i=1;i<n;i++){
        auto x  = lower_bound(a[t[i]-'a'].begin(),a[t[i]-'a'].end(),id);
        if(x==a[t[i]-'a'].end()){
            cout << -1 << endl;
            return 0;
        }
        id = *x;
        if(id>i){
            cout << -1 << endl;
            return 0;
        }
    }
    id = n-1;
    vector<int> p(n);
    for(int i=n-1;i>=0;i--){
        chmin(id,i);
        auto x = upper_bound(a[t[i]-'a'].begin(),a[t[i]-'a'].end(),id);
        x--;
        id = *x;
        p[i] = id;
    }
    vector<int> h(n);
    priority_queue<pair<int,int> > pq;
    int c = 0;
    for(int i=n-1;i>=0;i--){
        if(p[i]==i){
            h[i] = 0;
            while(!pq.empty())pq.pop();
            continue;
        }
        if(i==n-1){
            h[i] = 1;
            c++;
            pq.push(MP(p[i],c));
        }else{
            if(p[i]==p[i+1]){
                auto x = pq.top();
                int ss = x.second;
                int tt = x.first;
                
                tt -= (c-ss);
                if(tt >= i){
                    pq.pop();
                    auto y = pq.top();
                    h[i] = c-y.second +1 ;
                }else{
                    h[i] = h[i+1];
                }
            }else{
                c++;
                if(p[i]!=p[i+1]-1)pq.push(MP(p[i],c));
                h[i] = h[i+1]+1;
            }
        }
    }
    
    int mx = 0;
    rep(i,n){
        // cerr << h[i] << " ";
        chmax(mx,h[i]);
    }
    // cerr << endl;
    cout << mx << endl;
    return 0;
}

Measured memory_bytes: 17140
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
using namespace std;
#define N 200005
int n,fa[N],cnt,head[N],vis[N],mk[N],f[N],len;
struct edge{int to,nxt;}e[N];
void adde(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
/*void dfs(int u){
	for (int i=head[u];i;i=e[i].nxt) if (!mk[e[i].to]){
		dfs(e[i].to);
		vis[f[e[i].to]]=1;
	}
	int mex=0;while (vis[mex]) mex++;f[u]=mex;
	for (int i=head[u];i;i=e[i].nxt) if (!mk[e[i].to]) vis[f[e[i].to]]=0;
}*/

void dfs(int u){
    for(int tmp=head[u];tmp;tmp=e[tmp].nxt){
        int v=e[tmp].to;
        if(!mk[v])dfs(v);
    }
    for(int tmp=head[u];tmp;tmp=e[tmp].nxt){
        int v=e[tmp].to;
        if(!mk[v])vis[f[v]]=true;
    }
    for(;vis[f[u]];f[u]++);
    for(int tmp=head[u];tmp;tmp=e[tmp].nxt){
        int v=e[tmp].to;
        if(!mk[v])vis[f[v]]=false;
    }
}

int main(){
	scanf("%d",&n);
	rep (i,1,n) scanf("%d",&fa[i]),adde(fa[i],i);
	int now=1;
	for (;!vis[now];now=fa[now]) vis[now]=1;
	for (;!mk[now];now=fa[now]) mk[now]=1;
	memset(vis,0,sizeof(vis));
	int Mx=0,Mi=1e9;
	rep (i,1,n) if (mk[i]){
		dfs(i);len++;
		Mx=max(Mx,f[i]);
		Mi=min(Mi,f[i]);
	}
	if (Mx==Mi&&(len&1)) puts("IMPOSSIBLE");else puts("POSSIBLE");
	return 0;
}
/*
4
2 3 4 1
*/

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

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

// type
using ll = int_fast64_t;
using ull = uint_fast64_t;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

//container
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
#define ALL(v) v.begin(),v.end()

//repetition
#define REP(n) for(ll i=0; i<(n); i++)
#define REPj(n) for(ll j=0; j<(n); j++)
#define REPinit(i,a,n) for(ll i=(a); i<(n); i++)
#define REPinitj(j,a,n) for(ll j=(a); j<(n); j++)

//algorithm
#define SORT(c) sort((c).begin(),(c).end())
#define CONTAINER_ALL(a) a.begin(),a.end()

//constant

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//Optimizer
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


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

    int a, b, c;
    cin >> a >> b >> c;
    cout << (int)(a * b / 2) << endl;
    
    return 0;
}


Measured memory_bytes: 3608
poland = input().split()
n = len(poland)
stack = []
for i in range(n):
    if poland[i] == "+":
        stack.append(stack.pop(-2) + stack.pop(-1))
    elif poland[i] == "-":
        stack.append(stack.pop(-2) - stack.pop(-1))
    elif poland[i] == "*":
        stack.append(stack.pop(-2) * stack.pop(-1))
    else:
        stack.append(int(poland[i]))

print(str(stack[-1]))


Measured memory_bytes: 5604
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    for (int i = 0; i < 10000; i++) {
      int n = sc.nextInt();
      if (n == 0) break;
      else System.out.printf("Case %d: %d\n", i+1, n);
    }
  }
}



Measured memory_bytes: 66652
import sys
n, k = map(int, input().split())
s = list(input())

if len(s) == 1:
    print(0)
    sys.exit()
ans = 0
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        ans += 1
print(min(len(s)-1, ans+2*k))


Measured memory_bytes: 4028
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define V vector
template <typename T> bool chmin(T &a, const T &b) {if(a > b){a = b; return true;} return false;}
template <typename T> bool chmax(T &a, const T &b) {if(a < b){a = b; return true;} return false;}
template<typename A, size_t N, typename T> void Fill (A (&array)[N], const T & val) {fill ((T*)array, (T*)(array+N), val);}
V<int> dx = {-1, 1,  0, 0, -1, -1,  1, 1};
V<int> dy = { 0, 0, -1, 1, -1,  1, -1, 1};

// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
struct UnionFind {
    vector<int> d;
    UnionFind(int n=0): d(n,-1) {}
    int find(int x) {
        if (d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (d[x] > d[y]) swap(x,y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y);}
    int size(int x) { return -d[find(x)];}
};

int main () {
    int n, m; cin >> n >> m;
    V<int> q(n);//iはq[i]番目にある
    rep(i, n) {
        int p; cin >> p; p--;
        q[p] = i;
    }
    UnionFind uf(n);
    rep(i, m) {
        int x, y; cin >> x >> y; x--; y--;
        uf.unite(x, y);
    }
    int ans = 0;
    rep(i, n) {//iをi番目に持ってこれるか
        if (uf.same(i, q[i])) ans++;
    }
    cout << ans << endl;

    return 0;
}

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

int N;
int A[3005];

vector<int> To[3005];

bool Check(int u,int fa){
	for(auto v:To[u])
		if(v^fa&&A[u]>A[v]&&!Check(v,0))
			return true;
	return false;
}

int main(){
	int i,u,v;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
		scanf("%d",&A[i]);
	for(i=1;i<N;i++){
		scanf("%d%d",&u,&v);
		To[u].push_back(v);
		To[v].push_back(u);
	}
	for(i=1;i<=N;i++)
		if(Check(i,0))
			printf("%d ",i);
	return 0;
}

Measured memory_bytes: 384
/* ***********************************************
Author        :taciturnity
Created Time  :2020/2/21 8:23:51
File Name     :TEST.cpp
************************************************ */
 
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <cmath>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define INF 0x3f3f3f3f
#define rep(i,x,y) for(int i = x;i <= y;++i)
#define fori(i,x,y) for(int i = x;i >= y; -- i)
#define bug puts("--------------")
#define out(x) cout<<x<<'\n';
inline char gc(){char op[2];scanf("%s",op);return op[0];}
const int N = 1e6+10;
const double eps = 0.00000001;
const ll mod = 1e9 ;
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int d[2000+5][2000+5];
int cnt[2000];
int main(){
    int n = read(),x = read(),y = read();
    rep(i,1,n){
        rep(j,1,n){
            d[i][j] = abs(j-i);
        }
    }
    rep(i,1,n){
        rep(j,1,n){
            d[i][j] = min(d[i][j],d[i][x]+d[y][j]+1);
        }
    }
    rep(i,1,n){
        rep(j,i,n){
            cnt[d[i][j]]++;
        }
    }
    rep(i,1,n-1) cout<<cnt[i]<<endl;
    
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define ll long long
int main(){
  string S,T;
  cin>>S>>T;
  int ans=0;
  rep(i,S.size()){
    if(S==T) ans=1;
    T+=T[0];
    T.erase(0,1);
  }
  cout<<(ans?"Yes":"No")<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;

int n, m, k;
int a[MAX_N + 5], b[MAX_N + 5];
long long sa[MAX_N + 5], sb[MAX_N + 5];
long long ans = 0;

int main()
{
	//ios_base::sync_with_stdio(0);
	//cin.tie(0); cout.tie(0);
	scanf("%d %d %d", &n, &m, &k);
	sa[0] = sb[0] = 0;
	for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sa[i] = sa[i-1]+a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &b[i]);
        sb[i] = sb[i-1]+b[i];
    }
    for (int i = 0; i <= n && sa[i] <= k; i++)
    {
        long long t = upper_bound(sb+1, sb+1+m, k-sa[i])-1-sb+i;
        ans = max(ans, t);
        //cout << "#" << i << " " << ans << endl;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 8408
#include<bits/stdc++.h>
#define two(a) (1<<(a))
#define LINF (1ll<<61)
#define EPS (1e-14)
#define Lshift(a,b) (a<<b)
#define Rshift(a,b) (a>>b)
#define rep(a,b) for(a=0 ; a<b ; a++)
#define xrep(a,b,c) for(a=b ; a<c ; a++)
#define INF (1<<29)
#define swap(a,b) ( (a^=b) , (b^=a) , (a^=b) )
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5]|=1<<(x&31))
#define maxL (10000000>>5)+1
#define mod 1000000007
#define vi vector<int>
#define pii pair<int, int>
#define mii map<int, int>
#define si set<int>
#define pb push_back
typedef long long ll;
using namespace std;

char in[110][110];
int dp[110][110];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int h, w, i, j;
    cin >> h >> w;
    xrep(i, 1, h + 1) {
        xrep(j, 1, w + 1) {
            cin >> in[i][j];
        }
    }
    memset(dp, 0x2f, sizeof(dp));
    dp[0][0] = dp[0][1] = dp[1][0] = 0;
    in[0][1] = in[1][0] = '.';
    xrep(i, 1, h + 1) {
        xrep(j, 1, w + 1) {
            int tmp = dp[i][j];
            if (in[i][j - 1] != in[i][j]) {
                // cout << i << ' ' << j << endl;
                tmp = min(dp[i][j-1] + 1, tmp);
            } else  {
                tmp = min(dp[i][j-1], tmp);
            }
            if (in[i-1][j] != in[i][j]) {
                // cout << i << ' ' << j << endl;
                tmp = min(dp[i-1][j] + 1, tmp);
            } else {
                tmp = min(dp[i-1][j], tmp);
            }
            dp[i][j] = tmp;
        }
    }
    // cout << in[1][1] << ' ' << in[1][2] << ' ' << in[2][1] << ' ' << in[2][2] << endl;
    // xrep(i, 1, h + 1) {
    //     xrep(j, 1, w + 1) {
    //         cout << dp[i][j];
    //     }
    //     cout << endl;
    // }
    cout << (dp[h][w] + 1) / 2<< endl;
}


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

ll digit(ll a) {
  ll ans = 1;
  while (a >= 10) {
    a /= 10;
    ans++;
  }
  return ans;
}
int main() {
  ll N;
  cin >> N;
  ll ans;
  ll rN = sqrt(N);
  ll res = 0;
  ll anotherres = 0;
  for(ll i = rN; i >= 1; i--) {
    if (N % i == 0) {
      res = i; anotherres = N / i;
      break;
    }
  }
  ans = max(digit(res),digit(anotherres));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3668
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        long k = sc.nextLong();
        int arr[] = new int[n+1];
        for(int i=1;i<=n;i++)
        {
            arr[i] = sc.nextInt();
        }
        long befrep = 0;
        int start =1;
        int tr = 0;
        Map<Integer,Integer> map = new HashMap<>();
        while(true)
        {
            if(map.get(start)==null)
            {
                map.put(start,1);
                tr = start;
                start = arr[start];
                befrep = befrep+1;
            }
            else
            {

                break;
            }
        }

        long rep =1;
        int save =tr;


        while(true)
        {
            if(arr[save]==tr)
            {
                break;
            }
            else
            {
                rep++;
                save = arr[save];
            }
        }

        if(k>befrep) {
            long last = (k - befrep) % rep;
            int fin = tr;
            //int ans;
            for (int i = 0; i < last; i++) {
                fin = arr[fin];
            }
            System.out.println(arr[fin]);
        }
        else
        {
            int ans=0;
            int start2=1;
            for(int i=0;i<k;i++)
            {
                start2=arr[start2];
            }
            System.out.println(start2);
        }


    }
}

Measured memory_bytes: 68880
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=(2e5)+10;
int n,p[maxn],fa[maxn];
ll ans;
struct node {
	int x,y;
	friend bool operator < (node t1,node t2) {
		return (ll)t1.y*(t2.x+t2.y)<(ll)t2.y*(t1.x+t1.y);
	}
	friend node operator + (node t1,node t2) {
		return (node){t1.x+t2.x,t1.y+t2.y};
	}
} d[maxn],A;
set<pair<node,int> > s;
set<pair<node,int> >::iterator it;
int find(int x) {
	if (fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int main() {
	//freopen("1.txt","r",stdin);
	read(n);
	fa[1]=1;
	for (int i=2;i<=n;i++) read(p[i]),fa[i]=i;
	int x,y;
	for (int i=1;i<=n;i++) {
		read(x);
		if (!x) A=(node){1,0};
		else A=(node){0,1};
		if (i>1) s.insert(make_pair(A,i));
		d[i]=A;
	}
	for (int i=1;i<n;i++) {
		it=s.begin(); x=(*it).second;
		s.erase(it);
		y=find(p[x]);
		//printf("%d %d %d %d\n",x,y,d[y].x,d[y].y);
		ans+=(ll)d[x].x*d[y].y;
		if (y>1) {
			it=s.find(make_pair(d[y],y));
			assert(it!=s.end());
			s.erase(it);
		}
		fa[x]=y;
		d[y]=d[y]+d[x];
		if (y>1) s.insert(make_pair(d[y],y));
	}
	printf("%lld\n",ans);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Interger overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Measured memory_bytes: 16000
import sys
input = sys.stdin.readline
a,b=map(int,input().split())
cnt=0
for i in range(a,b+1):
    x=str(i)
    flg=True
    for j in range(len(x)):
        if x[j]!=x[-j-1]:
            flg=False
    if flg:cnt+=1
print(cnt)


Measured memory_bytes: 41196
main :: IO ()
main = do
  n <- read <$> getLine :: IO Int
  as <- map read . words <$> getLine :: IO [Int]
  let
    ls = init . scanl gcd 0 $ as :: [Int]
    rs = tail . scanr gcd 0 $ as :: [Int]
    m = maximum $ zipWith gcd ls rs :: Int
  print m


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

using namespace std;

typedef long long ll;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    float n; cin >> n;
    for(int i = 1; i < 10; i++){
        if(n/i == int(n/i) && (n/i) < 10){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
}



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

#define endl '\n'
#define int ll
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;
int n, k, a[N];

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

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

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

    int valid = false;
    for (int i = 0; i < n; i++)
    {
        if (a[i] - k >= 0) {
            if ((a[i] - k) % all_gcd == 0) {
                valid = true;
                break;
            }
        }
    }

    cout << ((valid) ? "POSSIBLE" : "IMPOSSIBLE");

    return 0;
}

Measured memory_bytes: 1024
from heapq import heappush, heappop
M, N, K = map(int, input().split())

X = [[] for i in range(M)]
Y = [[] for i in range(N)]

for i in range(K):
    x, y = map(int, input().split()); x -= 1; y -= 1
    X[x].append((y, i))
    Y[y].append((x, i))

G0 = [[] for i in range(K)]
G1 = [[] for i in range(K)]
for x in range(M):
    vs = X[x]
    if vs:
        vs.sort()
        prv = vs[0]
        for v in vs[1:]:
            d = v[0] - prv[0]
            G0[prv[1]].append((v[1], d))
            G0[v[1]].append((prv[1], d))
            prv = v
for y in range(N):
    vs = Y[y]
    if vs:
        vs.sort()
        prv = vs[0]
        for v in vs[1:]:
            d = v[0] - prv[0]
            G1[prv[1]].append((v[1], d))
            G1[v[1]].append((prv[1], d))
            prv = v

INF = 10**18
que = []
D0 = [INF]*K; D1 = [INF]*K
if X[0]:
    y0, k = X[0][0]
    que.append((y0, 0, k))
while que:
    cost, t, v = heappop(que)
    if not t:
        if D0[v] < cost:
            continue
        for w, d in G0[v]:
            if cost + d < D0[w]:
                D0[w] = cost + d
                heappush(que, (cost + d, 0, w))
        if cost + 1 < D1[v]:
            D1[v] = cost + 1
            heappush(que, (cost + 1, 1, v))
    else:
        if D1[v] < cost:
            continue
        for w, d in G1[v]:
            if cost + d < D1[w]:
                D1[w] = cost + d
                heappush(que, (cost + d, 1, w))
        if cost + 1 < D0[v]:
            D0[v] = cost + 1
            heappush(que, (cost + 1, 0, v))
ans = INF
if X[M-1]:
    y0, k = X[M-1][-1]
    ans = min(ans, D0[k] + (N-1-y0))
if Y[N-1]:
    x0, k = Y[N-1][-1]
    ans = min(ans, D1[k] + (M-1-x0))
if ans < INF:
    print(ans)
else:
    print(-1)



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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(n) n.begin(),n.end()

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	int N, Y;
	cin >> N >> Y;

	for(int x = 0; x <= N; x++){
		for(int y = 0; y <= N; y++){
			int z = N - x - y;
			if(z < 0 || z > N) continue;
			int sum = x*10000 + y*5000 + z*1000;
			if(sum != Y) continue;

			printf("%d %d %d\n", x, y ,z);
			return 0;
		}
	}
	printf("-1 -1 -1\n");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int64_t i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define COUTDOUBLE(d,i) cout << setprecision((i)) << (d) << endl;
#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}
#define MREP(i,m) for(auto i=(m).begin(); i != (m).end(); ++i) // auto key = i->first;auto value = i->second;

using namespace std;
typedef int64_t I;
typedef pair<I,I> P;
typedef vector<I> V;

I MOD = pow(10,9)+7;
I MAX = LONG_MAX;
I MIN = LONG_MIN;

// 最大公約数
I gcd(I a, I b) {
  return b != 0 ? gcd(b, a % b) : a;
}

// 最小公倍数
I lcm(I a, I b) {
  return a * b / gcd(a, b);
}

int ctoi(char c){
  return c - '0';
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  I n,k,r,s,p;
  string t;
  cin >> n >> k >> r >> s >> p >> t;
  V dp(n);
  I an=0;
  REP(i,n){
    if (i-k >=0 && t.at(i-k) == t.at(i) && dp.at(i-k) == 0){
      dp.at(i) = 1;
    }else{
      if (t.at(i) == 'r'){
        an += p;
      }else if (t.at(i) == 's'){
        an += r;
      }else if (t.at(i) == 'p'){
        an += s;
      }
    }
  }
  cout << an << endl;
  return 0;
}



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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

void Main(){
    VI t(5); REP(i,5) cin >> t[i];
    SORT(t);
    int ans = INF;
    do{
        int now = 0;
        REP(i,5){
            now = (now+9)/10*10;
            now += t[i];
        }
        chmin(ans, now);
    }while(next_permutation(ALL(t)));
    cout << ans << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int c5=0,c7=0,x,n=3;
    vector<int>v;
    while(n--)
    {
        cin>>x;
        if(x==5)c5++;
        else if(x==7)c7++;

    }
    if(c5==2&&c7==1)cout<<"YES";
    else cout<<"NO";
}


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

// #define ONLINE_JUDGE

#define V vector
#define P pair

using LL = long long;
#define FOR(i, x, y) \
    for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) \
    for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifndef ONLINE_JUDGE
#define dbg(x...)                             \
    do {                                      \
        cerr << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() { cerr << "\033[39;0m" << endl; }
template <template <typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
    for (auto v : a) cerr << v << ' ';
    err(x...);
}
template <typename T, typename... A>
void err(T a, A... x) {
    cerr << a << ' ';
    err(x...);
}
#else
#define dbg(...)
#endif
#define sz(x) (int)x.size()

LL bin(LL a, LL b, LL p) {
    LL res = 1;
    a = (a % p + p) % p;
    for (; b; b >>= 1, a = a * a % p)
        if (b & 1) res = res * a % p;

    return res;
}
const int N = 1e5+50;

char s[N];

int n;


void solve() {
    scanf("%s", s);
    n = strlen(s);
    int ans = 0;
    for (int i=0, j; i<n; i=j+1) {
        j = i;
        if (s[i] != 'R')
            continue;
        while (j+1 < n && s[j+1] == s[i]) {
            ++j;
        }
        ans = max(ans, j-i+1);
    }
    printf("%d\n", ans);
}

int main() {

    // int t;
    // cin >> t;
    // while (t--) solve();

    solve();

    return 0;
}

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

int main(){
	int max,ans,n,t;
	cin >> n;
	vector <int> c(n);
	vector <int> v(n);
	vector <int> p(n);
	for(int i=0;i<n;i++){
		cin >> v[i];
	}
	for(int i=0;i<n;i++){
		cin >> c[i];
	}
	max=0;
	t=0;
	ans=0;
	for(int i=0;i<n;i++){
		p[i] = v[i] - c[i];
	}
	for(int i=0;i<n;i++){
		max=0;
		for(int x=i;x<n;x++){
			if(max+p[x]>max){
				max += p[x];
			}
			else{
				continue;
			}
		}
		if(max>ans){
			ans = max;
		}
	}

	cout << ans;
	cin >> t;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int parent(int a, vector<int> &par) {
  if (par[a] == -1) return a;
  return par[a] = parent(par[a], par);
}

void unite(int a, int b, vector<int> &par, vector<int> &rank, vector<int> &cnt) {
  a = parent(a, par), b = parent(b, par);
  if (a == b) return;
  if (rank[a] < rank[b]) {
    par[a] = b;
    cnt[b] += cnt[a];
  }
  else {
    par[b] = a;
    if (rank[a] == rank[b]) ++rank[b];
    cnt[a] += cnt[b];
  }
}

int main() {
  int n, m, k; cin >> n >> m >> k;
  vector<int> par(n, -1), rank(n, 0), cnt(n, 1);
  vector<P> E;
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b; --a, --b;
    E.emplace_back(min(a,b), max(a,b));
    unite(a, b, par, rank, cnt);
  }
  for (int i = 0; i < k; ++i) {
    int c, d; cin >> c >> d; --c, --d;
    E.emplace_back(min(c,d), max(c,d));
  }
  
  for (int i = 0; i < n; ++i)
    cnt[i] = cnt[parent(i, par)];
  
  for (auto e:E) {
    int a = e.first, b = e.second;
    if (parent(a, par) == parent(b, par)) --cnt[a], --cnt[b];
  }
  
  for (int i = 0; i < n; ++i)
    cout << cnt[i]-1 << " ";
  cout << endl;
}

Measured memory_bytes: 4336
use std::io;
use std::str::FromStr;

fn input<T:FromStr>() -> T {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.trim().parse().ok().unwrap()
}

fn main() {
    let n: u64 = input();
    let mut sum = 0;
    for i in 1..(n+1) {
        if i % 5 != 0 && i % 3 != 0 {
            sum += i;
        }
    }
    println!("{}", sum);
}


Measured memory_bytes: 2168
#include<stdio.h>

int main() {
	int n, y,i,j,sum=0,count=0,a,b,c;
	scanf("%d %d",&n,&y);
	for(i = 0; i <= n; i++){
		for(j = i; j <= n; j++){
			sum = 10000 * i + 5000 * (j - i) + 1000 * (n - j);
			if(sum == y){
				count++;
				a=i;
				b=j-i;
				c=n-j;
			}
		}
	}
	if(count>0)printf("%d %d %d\n",a,b,c);
	else printf("-1 -1 -1\n");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
using ll=long long;
using namespace std;


int main(){
   cin.tie(0);
   ios::sync_with_stdio(false);
   cout << fixed << setprecision(20);
   
   //int n,ans; cin >> n;
   string s,ans; cin >> s;
   if(s=="Sunny") ans = "Cloudy";
   else if(s=="Cloudy") ans="Rainy";
   else ans="Sunny";
   //vector<int> a(n),b(n),c(n),d(n);

   cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N,K,s;
    cin >> N >> K;
    s = 0;
    for(int i = 0; i < N ; i++){
        int x,t;
        cin >> x;
        t = K-x;
        if(t<0){
            t *= -1;
        }
        if(t<x){
            s += 2*t;
        }
        else{
            s += 2*x;
        }
    }
    cout << s << endl;
}

Measured memory_bytes: 256
//Bismillahir Rahman-ir Rahim
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000002
#define PI acos(-1)
//#define m (pow(10, 9)+7)
typedef unsigned long long ull;
typedef long long ll;


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

    int A, B;
    cin >> A >> B;

    if(A > 8 || B > 8){
        cout << ":(" << endl;
    }
    else cout << "Yay!" << endl;
    


    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>


int main(){
    int set,call;
    int setAry[4], callAry[4];
    int setCnt[10], callCnt[10];
    int hit, used, blow;

    while (scanf("%d %d",&set, &call), set!=0){
        for (int i=0; i<10; i++){
            setCnt[i] = callCnt[i] = 0;
        }
        for (int i=0; i<4; i++){
            setAry[i] = set%10;
            set /= 10;
            setCnt[setAry[i]]++;
            callAry[i] = call%10;
            call /= 10;
            callCnt[callAry[i]]++;
        }
        used=0;
        for (int i=0; i<10; i++){
            if (setCnt[i] && callCnt[i] ) used++;
        }
        hit=0;
        for (int i=0; i<4; i++){
            if (setAry[i] == callAry[i]) hit++;
        }
        blow = used-hit;
        printf("%d %d\n", hit, blow);
    }    
    return 0;
}

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

using namespace std;

#define FOE(i, s, t) for (int i = s; i <= t; i++)
#define FOR(i, s, t) for (int i = s; i < t; i++)
#define FOD(i, s, t) for (int i = s; i >= t; i--)

#define LL long long
#define mp make_pair
#define pb push_back

#define K 500001
#define R (1 << 11)

int n, v[K], w[K];

vector<pair<int, int> > dect[K];
set<pair<int, int> > C[K];

int finish[K];

int solve(int a, int p) {
	if (p == 0) return 0;
	if (a == 0) return 0;

	int ret;

	if (a >= R) {
		return max(solve(a / 2, p), (p - w[a] >= 0 ? solve(a / 2, p - w[a]) + v[a] : 0));
	} else {
		if (!finish[a]) {
			finish[a] = 1;
			sort(dect[a].begin(), dect[a].end());	
			
			int last = 0;
			FOR(j, 0, dect[a].size()) {
				int we = dect[a][j].first;
				int val = -dect[a][j].second;
				
				if (val > last) {
					last = val;
					C[a].insert(mp(-we, val));	
				//	printf("%d: insert %d %d\n", a, -we, val);
				}
			}
		}
		
		if (C[a].lower_bound(mp(-p, -1)) == C[a].end()) {
			return 0;	
		} else {
			pair<int, int> T = *(C[a].lower_bound(mp(-p, -1)));
			
		//	printf("T = %d %d %d\n", T.first, T.second, (*(C[a].lower_bound(mp(-p, -1)))).second * -1);
			return (*(C[a].lower_bound(mp(-p, -1)))).second;	
		}
	}
}

void precompute(int u, int val, int we) {
	if (u >= R) return;
	if (we > 100000) return;
	
	dect[u].pb(mp(we, -val));
	precompute(u * 2, val, we);
	precompute(u * 2 + 1, val, we);
	
	val += v[u];
	we += w[u];

	dect[u].pb(mp(we, -val));
	precompute(u * 2, val, we);
	precompute(u * 2 + 1, val, we);
}

int main() {
//	freopen("1.in", "r", stdin);
	scanf("%d", &n);
	
	FOE(i, 1, n) {
		scanf("%d%d", &v[i], &w[i]);
	}
	
	precompute(1, 0, 0);
	cerr << clock() << endl;
	
	int q; scanf("%d", &q);
	
	int ret = 0;
	while (q--) {
		int q, p; scanf("%d%d", &q, &p);
		
		//ret += solve(q, p);
		printf("%d\n", solve(q, p));
	}
//	cout << ret << endl;
	cerr << clock() << endl;
}

Measured memory_bytes: 147252
n=input();l,r=int(n[:2])<1or int(n[:2])>12,int(n[2:])<1or int(n[2:])>12
if l and r:p="NA"
elif not(l or r):p="AMBIGUOUS"
elif l and not r:p="YYMM"
else:p="MMYY"
print(p)

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

const int MAX_N = 100;


int perm[MAX_N]; /* 各桁に何の数字を使ったか */
bool used[MAX_N]; // default は false



void display ( int array[], int n){
    for ( int i = 0; i < n; ++i){
        cout << array[i] << " ";
    }
    cout << endl;
}

bool check ( int n, int P[], int Q[] ){
    int flag = 0;
    for ( int i = 0; i < n; ++i){
        if ( P[i] != Q[i] ){
            flag += 1;
        }
    }
    if ( flag == 0 ){
        return true;
    } else {
        return false;
    }
}


int ans = 0;
int final_ans = 0;
/* 0 から n-1 までの数値の並び替え */
int permutation ( int pos, int n, int P[] ){
    if ( pos == n ){
        ans += 1;
        //cout << ans <<  endl;
        //display(perm, n);
        //display(P, n);
        if ( check(n,perm,P) ) {
            final_ans = ans;
            return final_ans;
        } else {
            return final_ans = 0;
        }
    }
    for ( int i = 0; i < n; ++i){
        if ( !used[i] ){
            perm[pos] = i;
            used[i] = true;
            final_ans = permutation(pos+1,n,P);
            if ( final_ans != 0 ){
                return final_ans;
            }
            used[i] = false;
        }
    }
    return final_ans;
}

int res,res1,res2;

int main(){
    int N;
    cin >> N;
    int P[N];
    int Q[N];
    int p,q;
    for ( int i = 0; i < N; ++i){
        cin >> p;
        P[i] = p - 1;
    }
    for ( int i = 0; i < N; ++i){
        cin >> q;
        Q[i] = q - 1;
    }
    res1 = permutation(0,N,P);
    ans = 0; final_ans = 0;
    for ( int i = 0; i < MAX_N; ++i){
        used[i] = false;
    }
    res2 = permutation(0,N,Q);
    res = max( res1 - res2, res2 - res1);
    // cout << res1 << res2 << res << endl;
    cout << res << endl;
    
    return 0;
}


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

int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    sort(A.begin(), A.end(), greater<long long>());

    if (N % 2 == 0) {
        long long res = 0;
        for (int i = 0; i < N/2 - 1; ++i) res += A[i] * 2;
        res += A[N/2 - 1];
        res -= A[N/2];
        for (int i = N/2 + 1; i < N; ++i) res -= A[i] * 2;
        cout << res << endl;
    }
    else {
        long long res1 = 0;
        for (int i = 0; i < N/2 - 1; ++i) res1 += A[i] * 2;
        res1 += A[N/2 - 1] + A[N/2];
        for (int i = N/2 + 1; i < N; ++i) res1 -= A[i] * 2;
        
        long long res2 = 0;
        for (int i = 0; i < N/2; ++i) res2 += A[i] * 2;
        res2 -= A[N/2] + A[N/2 + 1];
        for (int i = N/2 + 2; i < N; ++i) res2 -= A[i] * 2;
        cout << max(res1, res2) << endl;
    }
}

Measured memory_bytes: 1024
#include<bits/stdc++.h> 
using namespace std;
char s[100006];
int i,len;
int  main(){
	scanf("%s",s);
	len=strlen(s);
	int g=0,p=0,sum=0; 
	for(i=0;i<len;i++)
	{
		if(s[i]=='g')
		{
			if(g>p)
			{
				sum++;
				p++;
			}
			else
			g++;
		}
		else
		{
			if(g>p)
				p++;
			else
			{
				sum--;
				g++;
			}
		}
	}
	printf("%d\n",sum);
	return 0;
} 

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

int main(){
    int INF = 1'000'000'000;
    typedef pair<int, int> P;
    int k;
    cin >> k;
    vector<vector<P>> node(k);
    for (int i = 0; i < k; i++){
        node[i].push_back({(i+1)%k, 1});
        node[i].push_back({(i*10)%k, 0});
    }
    priority_queue<P, vector<P>, greater<P>> pq;
    vector<int> distance(k, INF);
    distance[1] = 0;

    pq.push({0, 1});
    while (pq.size() > 0){
        P p = pq.top(); pq.pop();
        //secondは行き先
        int v = p.second;
        //firstは距離
        if (distance[v] < p.first) continue;
        for (int i = 0; i < node[v].size(); i++){
            if (distance[node[v][i].first] > distance[v] + node[v][i].second){
                distance[node[v][i].first] = distance[v] + node[v][i].second;
                pq.push({distance[node[v][i].first], node[v][i].first});
            }
        }
    }

    cout << distance[0] + 1 << endl;
}

Measured memory_bytes: 6780
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = n % 1000;
		if(a == 0) System.out.println(0);
		else System.out.println(1000-a);
	}
}


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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define mod 1000000007LL
#define IN freopen("C.in","r",stdin)
#define OUT freopen("output.txt","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG pf("Hi\n")
#define MEM(ara,val) memset(ara,val,sizeof(ara))
#define INF 1000000000
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 2

using namespace __gnu_pbds;
using namespace std ;

typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<i64, i64> pii;

#define maxn 700

int g[maxn+5][maxn+5] ;

int col[maxn+5] , cnt[2] , n ;

bool dfs(int u ,int c)
{
//    printf("dfs %d %d\n",u,c) ;
    int ret = 1 ;
    cnt[c]++ ; col[u] = c ;
    for(int i=1 ; i<=n ; i++)
    {
        if(!g[u][i] || u==i) continue ;
        int v = i ;
        if( col[v]!=-1 && col[v]==c )
        {
  //          printf("false %d %d\n",u,v) ;
            ret = false ;
        }
        if( col[v]==-1 ) ret &= dfs(v,c^1) ;
    }
    return ret ;
}

int dp[705][705] ;

int main()
{
    MEM(col,-1) ;
    MEM(g,1) ;

    int i , j , k , m ;

    scanf("%d %d",&n,&m) ;

    for(i=1 ; i<=m ; i++)
    {
        int u , v ;
        scanf("%d %d",&u,&v) ;
        g[u][v] = 0 ;
        g[v][u] = 0 ;
    }
    int yes = 1 ;
    dp[0][0] = 1 ;
    for(i=1 ; i<=n ; i++)
    {
        if( col[i]==-1 )
        {
            cnt[0]= cnt[1] = 0 ;
            yes &= dfs(i,0) ;
            for(j=0 ; j+cnt[0]<=n ; j++) dp[i][j+cnt[0]] |= dp[i-1][j] ;
            for(j=0 ; j+cnt[1]<=n ; j++) dp[i][j+cnt[1]] |= dp[i-1][j] ;
        }
        else for(j=0 ; j<=n ; j++) dp[i][j] = dp[i-1][j] ;
    }
    int ans = (n*(n-1))/2 ;

    for(i=0 ; i<=n ; i++)
    {
        if( dp[n][i] ) ans = min( ans, (n*(n-1))/2 - (n-i)*i ) ;
    }

    if(!yes) printf("-1\n") ;
    else printf("%d\n",ans) ;

    return 0 ;
}


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

typedef long double                 ld;
typedef long long                   ll;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
typedef pair<string , string>       pss;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define F                           first
#define S                           second
#define sep                         ' '
#define endl                        '\n'
#define file_io                     freopen("input.txt" , "r+" , stdin) ; freopen("output.txt" , "w+" , stdout);
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define error(x)                    cerr << "$$$ " << x << '\n';
#define error2(x,y)                 cerr << "#F : " << x << "      #S : " << y << '\n';
#define kill(x)                     return cout << x << endl , 0;
#define pb                          push_back

const ll MXN = 3e3 + 3;
const ll MX5 = 3e5 + 3;
const ll MX6 = 1e6 + 3;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353;

ll power(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));
}
ll bmm(ll a,ll b){
    return (a%b==0 ? b : bmm(b,a%b));
}
string base2(ll n){
    string a="";while(n>=2){a+=(char)(n%2+'0');n/=2;}a+=(char)(n+'0');reverse(all(a));return a;
}
ll n, m, dp[MX5];
vector<ll> G[MX5];
bool vis[MX5];

void DFS(ll u){
    if(vis[u]) return;
    vis[u] = 1;
    ll maxi = 0;
    for(int i = 0; i < G[u].size(); i++){
        DFS(G[u][i]);
        maxi = max(maxi, dp[G[u][i]]);
    }
    dp[u] = maxi + 1;
    return;
}

int main(){
    //fast_io
    //file_io
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        ll a, b;
        cin >> a >> b;
        G[a].pb(b);
    }

    for(int i = 1; i <= n; i++){
        DFS(i);
    }

    cout << *max_element(dp,dp+MX5) - 1;
    return 0;
}
//! N.N


Measured memory_bytes: 13440
#include<stdio.h>
int main(void)
{
	int n,k,x,y,c=0;
	scanf("%d %d %d %d", &n, &k, &x, &y);
	if(n>k)
	{
		c=(n-k)*y;
		n=k;
	}
	c+=n*x;
	printf("%d\n", c);
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n,m,p;
	while(cin>>n>>m>>p,n){
		int sum=0,num[100];
		for(int i=0;i<n;i++){
			cin>>num[i];
			sum+=num[i];
		}
		if(num[m-1])cout<<(int)(sum*(float)(100-p)/num[m-1])<<endl;
		else cout<<0<<endl;
	}
}

Measured memory_bytes: 1160
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;
using ll = long long;

constexpr static ll MOD = 1000000007ll;
constexpr static int INF = 1 << 28; // for x <= 10^9
constexpr static ll INFL = 1ll << 60; // for x <= 10^19

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

    vector<double> vs(n);
    for (int i = 0; i < n; i++) {
        cin >> vs[i];
    }
    sort(vs.begin(), vs.end());
    double ans = vs[0];
    for (int i = 1; i < n; i++) {
        ans = (ans + vs[i]) / 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())
SS = []
SD = []
for i in range(N):
    s, t = input().split()
    SS.append(s)
    SD.append(int(t))

X = input()
count = 0
play = False
for i in range(1, N):
    if SS[i-1] == X: play = True
    if play: count += SD[i]

print(count)


Measured memory_bytes: 38448
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int maxn=100005;
int n,a[maxn];
ll sum[maxn];
template<class Type>Type read(){
    Type res=0,f_f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f_f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)-'0'+ch,ch=getchar();
    return res*f_f;
}
#define iread() (read<int>())
#define lread() (read<long long>())
#define ulread() (read<unsigned long long>())
int main(){
    n=iread();
    for (int i=1;i<=n;i++){
        a[i]=iread();
    }
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    int now=n;
    for (int i=n-1;i;i--){
        if((sum[i]<<1)<a[i+1]) break;
        now=i;
    }
    printf("%d\n",n-now+1);
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;

#define ALL(a) (a).begin(),(a).end()
#define ZP(a, len) setfill('0') << setw(len) << right << a
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
const ll LINF = 1e11;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

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

    int n;
    cin >> n;
    vi h = vi(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    int ans = 1;
    int hmax = h[0];
    for (int i = 1; i < n; ++i) {
        if(hmax <= h[i]){
            ans ++;
        }
        hmax = max(h[i], hmax);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import math

A, B, H, M = map(int, input().split())

h = H / 12 * 360 + M / 2
m = M / 60 * 360

d = min(360 - abs(h-m), abs(h-m))
C = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(math.radians(d)))

print(C)


Measured memory_bytes: 9496
N, K = map(int, input().split())
if K > ((N - 1) * (N - 2)) // 2:
	print(-1)
else:
	print(N - 1 + ((N - 1) * (N - 2)) // 2 - K)
	for i in range(N - 1):
		print(1, i + 2)
	s = 2
	t = 3
	for i in range(((N - 1) * (N - 2)) // 2 - K):
		if t <= N:
			print(s, t)
			t += 1
		else:
			s += 1
			t = s + 1
			print(s, t)
			t += 1

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

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;
    A.sort();
    long ans = 0;

    foreach (i; 0..N) {
        foreach (j; i+1..N) {
            auto ub = A.assumeSorted.lowerBound(A[i] + A[j]).length.to!long;
            auto lb = A.assumeSorted.lowerBound(A[j] - A[i]).length.to!long;
            lb = max(lb, j.to!long);
            if (lb >= ub) continue;
            long v = ub - lb;
            if (i >= lb && i < ub) v -= 1;
            if (j >= lb && j < ub) v -= 1;
            ans += v;

        }
    }

    ans.writeln;
}


Measured memory_bytes: 380
#include <bits/stdc++.h>
using Int = int64_t;
using UInt = uint64_t;
using C = std::complex<double>;
#define rep(i, n) for(Int i = 0; i < (Int)(n); ++i)
#define guard(x) if( not (x) ) continue;
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif

int main() {
   Int n, m;
   std::cin >> n >> m;
   Int res = 0;
   if( m == 0 ) {
      res = n * n;
   }
   else {
      for(Int b = 1; b <= n; ++b) {
         guard( b > m );
         Int t = (n/b)*(b-m)+std::max((Int)0, n%b-m+1);
         res += t;
      }
   }
   printf("%ld\n", res);
}


Measured memory_bytes: 256
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE BangPatterns #-}
module Main where

import           Data.List
import           Control.Monad
import           Debug.Trace
import qualified Data.ByteString.Char8         as BC
import           Data.Maybe                     ( fromJust, fromMaybe )
import qualified Data.Set                      as S
import qualified Data.IntMap.Strict            as IM
import qualified Data.IntMap.Lazy            as IML
import qualified Data.Map.Strict               as M
import           Data.Char
import qualified Data.Array.IArray as A
import qualified Data.Array.Unboxed as UA
import Data.Bits
import Control.Monad.State.Strict
import qualified Data.Array.ST as STA
import qualified Data.Array.IO as IOA
import qualified Data.Array.MArray as MA
import Control.Monad.ST
import System.IO (stdin)
import Control.Arrow
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Generic as GV



readTuple2 :: IO (Int, Int)
readTuple2 = do
    [a, b] <- readInts
    return (a, b)

readTuple3 :: IO (Int, Int, Int)
readTuple3 = do
    [a, b, c] <- readInts
    return (a, b, c)

readInt :: IO Int
readInt = fst . fromJust . BC.readInt <$> BC.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

split :: (a -> Bool) -> [a] -> [[a]]
split f [] = []
split f as =
    let (fo, la) = span f as
        las      = case la of
            [] -> []
            xs -> split f $ tail xs
    in  case fo of
            [] -> las
            xs -> xs : las

isEvenS :: BC.ByteString -> Bool
isEvenS s = let
    (a, b) = BC.splitAt (BC.length s `div` 2) s
    in
    a == b

main :: IO ()
main = do
    s <- BC.reverse <$> BC.getLine
    print $ (BC.length s -) $ head $ filter (\ind -> isEvenS $ BC.drop ind s) [1..]


Measured memory_bytes: 380