akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  for(int i=0;i<n;i++){
    if(a[i]%2==0){
      if(a[i]%3==0 or a[i]%5==0);
      else{
        cout<<"DENIED";
        return 0;
      }
    }
  }
  cout<<"APPROVED";
  return 0;
}

Measured memory_bytes: 256
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

def main():
  n,m=nii()

  tree=[[] for i in range(n)]
  for i in range(m):
    a,b=nii()
    a-=1
    b-=1
    tree[a]+=[b]
    tree[b]+=[a]

  for i in tree[0]:
    for j in tree[i]:
      if j==n-1:
        print('POSSIBLE')
        exit()
  print('IMPOSSIBLE')

if __name__=="__main__":
  main()

Measured memory_bytes: 38320
#include<bits/stdc++.h>
using namespace std;
typedef long long a;
typedef unsigned long long b;
int c[2003];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int x,y,z;
	cin>>x>>y>>z;
	int s;
	for(int i=1;i<=x;i++)
		for(int j=i+1;j<=x;j++)
		{
			s=min(min(abs(j-i),abs(i-y)+1+abs(j-z)),abs(i-z)+1+abs(j-y));
			c[s]++;
		}
	for(int i=1;i<=x-1;i++)
		cout<<c[i]<<endl;
}

Measured memory_bytes: 256
def main():
    n=int(input())
    a=sorted(list(map(int,input().split(' '))),reverse=True)
    next=0
    long=0
    short=0
    for i in range(n-1):
        if a[i] == a[i+1]:
            long = a[i]
            next=i+2
            break
    for j in range(next,n-1):
        if a[j] == a[j+1]:
            short = a[j]
            break
    print(long*short)



if __name__ == '__main__':
    main()


Measured memory_bytes: 14252
import java.util.Scanner;

public class Main {

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

        int n = sc.nextInt();
        // スペース区切りの整数の入力
        int[] value = new int[n];
        int[] cost = new int[n];
        int[] trueValue = new int[n];
        int max = 0;

        for(int i = 0; i < n; i++){
            value[i] = sc.nextInt();
        }
        for(int i = 0; i < n; i++){
            cost[i] = sc.nextInt();
        }
        for(int i = 0; i < n; i++){
            trueValue[i] = value[i] - cost[i];
            if(trueValue[i] > 0){
                max += trueValue[i];
             }
        }
        System.out.println(max);
    }
}

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	string s; cin>>s;
	int n = s.size();
	for(int i = 1; i < n; i++){
		if(s[i] == s[i - 1]){
			cout<<i<<" "<<i + 1<<endl;
			exit(0);
		}
		if(i > 1 && s[i] == s[i - 2]){
			cout<<i - 1<<" "<<i + 1<<endl;
			exit(0);
		}
	}
	cout<<"-1 -1"<<endl;

	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1001001001;

ll f(ll h, ll w, bool frag){
  vector<ll> piece(3);
  piece[0] = (frag ? h/3: h/3+1) *w;
  h -= (frag ? h/3: h/3+1);
  if(h%2 == 0 || w%2 == 0){
    piece[1] = h *w /2;
    piece[2] = h *w /2;
  }else{
    piece[1] = max(h,w) /2 *min(h,w);
    piece[2] = (max(h,w) /2 +1) *min(h,w);
  }
  sort(piece.begin(),piece.end());
  return piece[2] -piece[0];
}

int main(){
  ll h, w;
  cin >> h >> w;
  if(h%3 == 0 || w%3 == 0){
    cout << 0 << endl;
    return 0;
  }
  ll ans = INF;
  ans = min(ans, f(h,w,true));
  ans = min(ans, f(h,w,false));
  ans = min(ans, f(w,h,true));
  ans = min(ans, f(w,h,false));
  cout << ans << endl;
}

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

int main () {
  int N, c=0;
  cin >> N;
  for (int i=1; i<=N; i++) {
    int tmp;
    cin >> tmp;
    if (tmp!=i)
      c++;
  }
  if (c<=2)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}

import           Control.Monad
import           Control.Monad.ST
import           Data.Array.ST
import           Data.Array.Unboxed
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe
import           Data.Sequence         (Seq, ViewL (..), ViewR (..), (<|), (><),
                                        (|>))
import qualified Data.Sequence         as S
readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getIntList = readIntList <$> BS.getLine
type Pos = (Int,Int)
main = do
    [h,w] <- getIntList
    a <- map (/= '#') . concatMap BS.unpack <$> replicateM h BS.getLine
    let grid = listArray ((0,0),(h-1,w-1)) a
        init = S.fromList $ zip [(y,x) | x <- [0..w-1],y <- [0..h-1],not $ grid ! (y,x)] (repeat 0)
    print $ bfs (h-1,w-1) grid init
    return()

next :: STUArray s Pos Bool -> Pos -> Pos -> ST s (Seq Pos)
next g (h',w') (y,x) = do
    let list = [(ny,nx) | (dy,dx) <- zip [0,1,0,-1] [1,0,-1,0],let ny=y+dy,let nx=x+dx,0 <= ny && ny <= h' && 0 <= nx && nx <= w']
    vals <- zip list <$> mapM (readArray g) list
    let list' = [p | (p,v) <- vals,v]
    return $ S.fromList list'

bfs :: Pos -> UArray Pos Bool -> Seq (Pos,Int) -> Int
bfs s grid init = runST $ do
    g <- thaw grid :: ST s (STUArray s Pos Bool)
    f g init
    where   f :: STUArray s Pos Bool -> Seq (Pos,Int) -> ST s Int
            f !g !seq = case S.viewl seq of
                S.EmptyL  -> return 0
                ((p,d) :< ps) ->
                    do
                        !ne <- next g s p
                        let !ne' = S.zip ne (S.replicate 4 (d+1))
                        forM_ ne $ \(ny,nx) -> writeArray g (ny,nx) False
                        !v <- f g (ps><ne')
                        return $ max d v


Measured memory_bytes: 285756
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define int long long
#define endl "\n"
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr(a,b,c) for(int a=b; a<c; a++)
#define frr(a,b,c) for(int a=b;a>=c;a--)
#define pb push_back
#define pii pair<int,int>
#define R(a) ll a; cin >> a;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;

#define RA(a, n) ll a[(n) + 1] = {}; fr(i, 1, (n)+1) {cin >> a[i];}
#define RM(a, n, m) int a[n + 1][m + 1] = {}; fr(i, 1, n+1) {fr(j, 1, m+1) cin >> a[i][j];}
#define reset(X) memset(X, 0, sizeof(X))
using vi=vector<int>;
const int inf = 1e18;
const int mod=998244353;
unsigned int power(int x, unsigned int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
bool isPrime(int n)
{   if (n <= 1)  return false;
    if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;
    return true;
}
int modInverse(int n, int p)
{
    return power(n, p-2, p);
}

bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}
signed main()
{
    fastio;
    R(x);R(n);
    RA(a,n);
    map<int,int>m;
    fr(i,1,n+1)
    {
        m[a[i]]=1;
    }
    int l=x,r=x;
    while(true)
    {
        //cout<<l<<" "<<r<<" "<<m[l]<<" "<<m[r]<<endl;
        if(m[l]==0||m[r]==0)
        {
            cout<<(m[l]==0?l:r);
            return 0;
        }
        l-=1;
        r+=1;
    }
}


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


int main() {
    string S;
    cin >> S;
    
    int y = 700;
    for(int i = 0; i < 3; i++) {
        if(S[i] == 'o') {
            y += 100;
        }
    }
    
    cout << y << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
ll gcd(ll a, ll b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region LCM
ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int h, w, m; cin >> h >> w >> m;
	map<int, int> mpX;
	map<int, int> mpY;
	map<pair<int, int>, bool> mpXY;
	rep(i, m)
	{
		int x, y; 
		x = i, y = i;
		cin >> x >> y;
		--x, --y;
		++mpX[x];
		++mpY[y];
		mpXY[{x, y}] = true;
	}
	int mxX = 0, mxY = 0;
	vector<int> X, Y;
	for (auto p : mpX)chmax(mxX, p.second);
	for (auto p : mpY)chmax(mxY, p.second);
	for (auto p : mpX)if (p.second == mxX)X.push_back(p.first);
	for (auto p : mpY)if (p.second == mxY)Y.push_back(p.first);
	for (int x : X)for (int y : Y)
	{
		if (!mpXY[{x, y}])
		{
			cout << mxX + mxY << endl;
			return 0;
		}
	}
	cout << mxX + mxY -1 << endl;
}

Measured memory_bytes: 54312
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i,n) for (int i = (int)(n)-1; i>=0; --i)
#define For(i,a,b) for(auto i=(a);i<=(b);++i)
#define rFor(i,a,b) for(auto i=(b);i>=(a);--i)
#define call(var) cerr<<#var<<"="<<var<<"\n";
#define dup(x,y) (((x)+(y)-1)/(y))
#define all(x) (x).begin(),(x).end()
using ll=long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;
const double pi = acos(-1);
template<class t,class u> inline bool chmax(t&a,u b){if(a<b){a=b;return true;}return false;}
template<class t,class u> inline bool chmin(t&a,u b){if(b<a){a=b;return true;}return false;}
template<class T> istream& operator>>(istream& is, vector<T>& a){rep(i,a.size()) is >> a[i]; return is;}
template<class T> ostream& operator<<(ostream& os, vector<T>& a){rep(i,a.size()) os << a[i] << " "; return os;}
template<class T, class U> istream& operator>>(istream& is, pair<T,U>& p){is >> p.first >> p.second; return is;}
template<class T, class U> ostream& operator<<(ostream& os, const pair<T,U>& p){os << "("<< p.first << "," << p.second << ")"; return os;}
template<class T, class U> ostream& operator<<(ostream& os, const map<T,U>& mp){for(auto& t : mp) os << t.first << " " << t.second << "\n"; return os;}

int main(){
    int n;cin >> n;
    vi p(n);
    cin >> p;
    int ans = 0;
    rep(i,n-2){
        int s = p[i] + p[i+1] + p[i+2];
        s -= max({p[i], p[i+1], p[i+2]}) + min({p[i], p[i+1], p[i+2]});
        if(s == p[i+1]) ++ans;
    }
    cout << ans << endl;
}

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

#define re return
#define pb push_back
#define po pop_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define fill(x, y) memset(x, y, sizeof(x))


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;

const int maxn = 1e5;
ll a[maxn], b[maxn];

int main() {
    int n;
    scanf("%d", &n);
    fo(i, n) scanf("%lld", a + i);
    fo(i, n) scanf("%lld", b + i);
    ll k1 = 0, k2 = 0; /// need to a, need to b
    fo(i, n) {
        if (a[i] == b[i]) continue;
        if (a[i] > b[i]) {
            k2 += a[i] - b[i];
        } else {
            k1 += b[i] - a[i];
            if ((ll)1 & (b[i] - a[i])) ++k1, ++k2;
        }
        //cout << k1 << ' ' << k2 << endl;
    }
    if (k2 * 2 <= k1) cout << "Yes" << endl;
    else cout << "No" << endl;
    re 0;
}


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

#define sz(a) (int)a.size()
#define re return
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(), a.end()
#define gr greater <int>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")

using namespace std;

typedef long long ll;
typedef string str;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;

///!!!<3<3<3<3<3!!!
void ProdamGaraje () {
   int a, b, c, k;
   cin >> a >> b >> c >> k;
   if (k <= a + b)
      cout << min (a, k);
   else
      cout << a - (k - a - b);
}
///!!!<3<3<3<3<3!!!
int main () {
   //freopen ("input.txt", "r", stdin);
   //freopen ("output.txt", "w", stdout);
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   int tt = 1;
   //cin >> tt;
   while (tt--)
      ProdamGaraje ();
}
///GOOOOOOSE!!!!
/*
     ▄▀▀▀▄
▄███▀░0░░░▌
    ▌░░░░░▐
    ▌░░░░░▐
     ▌▌ ▌▌
     ▌▌ ▌▌
     ▌▌ ▌▌
     ▌▌ ▌▌
     ▌▌ ▌▌
   ▄▄▌▌▄▌▌        */


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

int main()
{
	int a, b, c, d;
	scanf("%d %d %d %d", &a, &b, &c, &d);
	ll nax1 = max(a, b);
	ll nax2 = max(c, d);
	ll nin1 = min(a, b);
	ll nin2 = min(c, d);
	
	printf("%lld\n", max({nax1 * nax2, nax1 * nin2, nin1 * nax2, nin1 * nin2}));
	return 0;
}


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

bool check(int n,int i,map<char,int> m){
    int max1=0,max2=0;
    char c1,c2;
    for(pair<char, int> p:m){
        if(max1<p.second){
            max1=p.second;
            c1=p.first;
        }
    }
    m[c1]=0;
    if(m.size()==1){
        max2=0;
    }
    else{
        for(pair<char, int> p:m){
            if(max2<p.second){
                max2=p.second;
                c2=p.first;
            }
        }
    }
    if(max1>max2+(n-i-1)){
        cout<<c1<<" "<<i+1<<endl;
        return true;
    }
    return false;
}

void solve(int n){
    map<char,int> m;
    int i;
    char c;
    for(i=0;i<n;i++){
        cin>>c;
        if(m.find(c)!=m.end())m[c]+=1;
        else m[c]=1;
        if(check(n,i,m)){
            for(int j=i+1;j<n;j++){
                cin>>c;
            }
            return;
        }
    }
    
    cout<<"TIE"<<endl;
}


int main(void){
    int a;
    while(cin>>a,a){
        solve(a);
    }
}

Measured memory_bytes: 3128
package main

import "fmt"

func main() {
	var n int
	var as []int
	var bs []int
	var cs []int
	fmt.Scanf("%d", &n)
	for i := 0; i < n; i++ {
		var tmp int
		fmt.Scanf("%d", &tmp)
		as = append(as, tmp)
	}
	for i := 0; i < n; i++ {
		var tmp int
		fmt.Scanf("%d", &tmp)
		bs = append(bs, tmp)
	}
	for i := 0; i < n-1; i++ {
		var tmp int
		fmt.Scanf("%d", &tmp)
		cs = append(cs, tmp)
	}
	fmt.Println(exec(as, bs, cs))
}

func exec(as, bs, cs []int) int {
	var s int
	for i, a := range as {
		s += bs[a-1]
		if i < len(as)-1 && a+1 == as[i+1] {
			s += cs[a-1]
		}
	}
	return s
}

Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(void){
  long a, b;
  cin >> a >> b;
  if (a > b){
    int temp = b;
    b = a;
    a = temp;
  }
  long aa, bb, ii;
  aa = a;
  bb = b;
  ii = 1;
  for(int i = 2; i <= a ; i++){
    int flg = 0;
    do{
      flg = 0;
      if(aa % i == 0 && bb % i == 0){
        aa = aa / i;
        bb = bb / i;
        ii *= i;
        flg = 1;
      } 
    }while(flg == 1);
  }
  cout << bb * a;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
ll n;
ll h[100010];
int main(){
    cin>>n;
    for(int i = 0;i < n; i++){
        cin>>h[i];
    }
    int ans=0;
    int cnt=0;
    for(int i = 0;i <n-1; i++){
        if(h[i]>=h[i+1]) {
            cnt++;
            //cout<<h[i]<<" "<<h[i+1]<<endl;;
            //cout<<"cnt"<<" "<<cnt<<endl;
            ans=max(ans,cnt);
            //cout<<"new_ans"<<" "<<ans<<endl;
        }
        else cnt=0;
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(){
  int a,b,c,k,ans;
  cin >> a >> b >> c >> k;
  if(k<a){
    ans=k;
  }else if(k<=a+b){
    ans=a;
  }else{
    ans=-k+a+b+a;
  }
  cout << ans << endl;
  return 0;
}     

Measured memory_bytes: 3620
#!/usr/bin python3
# -*- coding: utf-8 -*-

import numpy as np
n, m, q = map(int, input().split())
x = np.zeros((n,n), dtype = int)
for _ in range(m):
    l, r = map(int, input().split())
    x[r-1][l-1] += 1
x.cumsum(out = x, axis = 0)
for i in range(n):
    x[i] = np.cumsum(x[i][::-1])[::-1]

for _ in range(q):
    l, r = map(int, input().split())
    print(x[r-1][l-1])


Measured memory_bytes: 28744
// OURL: https://atcoder.jp/contests/abc165/tasks/abc165_d
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define RREP(i,a,n) for(int i=(a),i##_len=(n);i<i##_len;++i)
#define MAT1D(V,T,a) vector<T> V (a)
#define MAT2D(V,T,a,b) vector<vector<T>> V (a, vector<T>(b))
#define MAT3D(V,T,a,b,c) vector<vector<vector<T>>> V (a, vector<vector<T>>(b, vector<T>(c)))

// http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){ return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));  }

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}
template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){ for(auto &e:t) fill_v(e,v);  }

template <typename A>
string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", ";  } first = false; res += to_string(x);  } res += "}"; return res;  }

string to_string(string s) { return '"' + s + '"';  }
string to_string(const char* s) { return to_string((string) s);  }
string to_string(bool b) { return (b ? "true" : "false");  }
string to_string(vector<bool>::reference b) { return to_string(bool(b));  }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";  }
template <typename A>
string to_string(vector<vector<A>> v) { string res; for(const auto &x : v) {res+="\n ";res += to_string(x);} return res; }

void debug_out() { cerr << endl;  }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...);  }

#ifdef LOCAL
#define debug(...) cerr << "[L" << to_string(__LINE__) << ":" <<#__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

  double a, b, n;
  cin >> a >> b >> n;
  ll x = 0;
  if (n < b) {
    x = n;
  } else {
    x = b - 1;
  }

  double t = x / b;

  cout << floor(a*t) << endl;


  return 0;
}


Measured memory_bytes: 3844
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<list>
#include<set>
#include<string>
using namespace std;
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		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;
	}
};
typedef long long ll;

const ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}
ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
int compare(string a, string b) {
	int i;
	for (i = 0; i < a[i] != '\0'; i++) {
		if (b[i] == '\0')
			return -1;
		else if (a[i] < b[i])
			return 1;
		else if (a[i] > b[i])
			return -1;
	}
	if (b[i] != '\0')
		return 1;
	else
		return 0;
}
int main() {
	int n, r, i, j,k, v[55], ans = 0,rv[55],p[55],t;
	cin >> n >> r;
	for (i = 0; i < n; i++) {
		cin >> v[i];
		rv[n - i - 1] = v[i];
	}
	for (i = 0; i <= r&&i <= n; i++) {
		for (j = 0; i + j <= r && i + j <= n; j++) {
			t = 0;
			for (k = 0; k < i; k++) {
				t += v[k];
				p[k] = v[k];
			}
			for (k = 0; k < j; k++) {
				t += rv[k];
				p[k + i] = rv[k];
			}
			sort(p, p + i + j);
			for (k = 0; k < r - i - j&&k<i+j; k++)
				if (p[k] < 0)
					t -= p[k];
			if (t > ans)
				ans = t;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 4992
from heapq import heapify, heappop, heappush

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

q = [(-val, i) for i, val in enumerate(b) if val != a[i]]
heapify(q)

# 3print(q)

cnt = 0

while q:
  bval, i = heappop(q)
  bval = - bval - a[i]
  dv, bval = divmod(bval, b[i - 1] + b[(i + 1) % n])
#   print(dv, bval,i)
  if dv == 0:
    print(-1)
    exit()
  bval += a[i]
  b[i] = bval
  cnt += dv
  if bval != a[i]:
    heappush(q, (- bval, i))
print(cnt)


Measured memory_bytes: 124764
import scala.io.StdIn._
object Main extends App {
  val Array(n, k) = readLine.split(" ").map(_.toInt)
  val vs = readLine.split(" ").map(_.toInt)
  val sums = vs.scanLeft(0)(_ + _)
  val total = sums(n)
  val minuss = vs.zipWithIndex.filter(_._1 < 0).sorted
  var max = 0
  for {
    l <- (0 to Math.min(n, k))
    r <- (0 to Math.min(n, k) - l)
  } {
    val sum = sums(l) + total - sums(n - r)
    val nDrop = Math.min(k - l - r, l + r)
    val inRange: Int => Boolean = (i => (0 <= i && i < l) || (n - r < i && i <= n))
    val drops = minuss.filter(z => inRange(z._2)).take(nDrop).map(_._1).sum
    max = Math.max(max, sum - drops)
  }

  println(max)
}

Measured memory_bytes: 31272
#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();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

#define F first
#define S second
//((cost, dir), (y, x))
typedef pair<pii, pii> State;

enum {kStraight = 0, kRight, kBack, kLeft, kHalt};
enum {kEast = 0, kSourth, kWest, kNorth};

vi dx = { 1, 0,-1, 0};
vi dy = { 0, 1, 0,-1};

int main(void){
    for(int w, h; cin >> w >> h, w;){
        vvi field(h, vi(w));
        rep(y, h) rep(x, w) cin >> field[y][x];

        vi cost(4);
        for(auto& c : cost) cin >> c;

        priority_queue<State, vector<State>, greater<State>> q;
        q.push(mp(mp(0, kEast), mp(0, 0)));

        map<pair<int, pii>, int> used;
        int res;
        while(!q.empty()){
            pii cur_pos = q.top().S;
            int cur_cost = q.top().F.F;
            int cur_dir = q.top().F.S;
            q.pop();

            used[mp(cur_dir, cur_pos)] = true;
            if(cur_pos == mp(h - 1, w - 1)){
                res = cur_cost;
                break;
            }

            rep(op, 4){
                int next_cost = cur_cost;
                if(field[cur_pos.F][cur_pos.S] != op) next_cost += cost[op];

                pii next_pos = cur_pos;
                int next_dir = (cur_dir + op) % 4;
                next_pos.F += dy[next_dir];
                next_pos.S += dx[next_dir];

                if(next_pos.F < 0 || h <= next_pos.F ||
                   next_pos.S < 0 || w <= next_pos.S) continue;
                if(used[mp(next_dir, next_pos)]) continue;

                q.push(mp(mp(next_cost, next_dir), next_pos));
            }
        }
        cout << res << endl;
    }

	return 0;
}

Measured memory_bytes: 1496
#include <stdio.h>
#define num 100

int main(){
int i,j,N,A[num],flag,count=0,key;

scanf("%d",&N);

for(i=0;i<N;i++){
scanf("%d",&A[i]);
}

flag=1;
i=0;

while(flag){
    flag=0;
    for(j=N-1;j>0;j--){
        if(A[j]<A[j-1]){
        key=A[j];
        A[j]=A[j-1];
        A[j-1]=key;
        count++;
        flag=1;
        }
        i++;
    }
}

for(j=0;j<N-1;j++){
printf("%d ",A[j]);
}

printf("%d\n%d\n",A[N-1],count);

return 0;
}

Measured memory_bytes: 600
def solve():
    a, b, c, d = [c for c in input()]
    conversion = {"0": "+", "1": "-"}
    for i in range(2 ** 3):
        b3, b2, b1 = list('{:03b}'.format(i))
        formula = str(a) + conversion[b3] + str(b) + conversion[b2] + str(c) + conversion[b1] + str(d)
        result = eval(formula)
        if result == 7:
            return formula + "=7"


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 3060
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	aa := make([]int, n)
	for i := 0; i < n; i++ {
		aa[i] = getNextInt(scanner)
	}
	l := aa[0]
	for i := 1; i < n; i++ {
		l = lcm(l, aa[i])
	}
	fmt.Fprintln(writer, l)
}
func gcd(m, n int) int {
	if n == 0 {
		return m
	}
	return gcd(n, m%n)
}
func lcm(m, n int) int {
	return m / gcd(m, n) * n
}



Measured memory_bytes: 1212
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
print((N+M)*(N+M-1)//2 -N*M)

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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef long long int64;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define GSORT(x) sort(all(x), greater<int>())
#define MIN(x) *min_element(all(x))
#define MAX(x) *max_element(all(x))
#define in(x) cin >> x
#define co(x) cout << x
#define el  cout << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


int main() {
    int n;
    std::string a, b, ans;
    cin >> n;
    cin >> a;
    cin >> b;
    for (int i = 0; i < n; ++i) {
        ans = ans + a[i] + b[i];
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
// *********************************************************************************
// *                        MURTAZA MUSTAFA KHUMUSI                                *
// *                        NIT-DGP,CSE - 2019-2023                                *
// *********************************************************************************

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007;
#define loop(i, a, n) for (int i = a; i < n; i++)
#define loop1(i, b, n) for (int i = b; i <= n; i++)
#define loopit(a) for (auto it = a.begin(); it != a.end(); it++)
#define ms(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define pi pair<int, int>
#define ff first
#define ss second
#define bloop(i, a, b) for (int i = a; i > b; i--)
#define bloop1(i, a, b) for (int i = a; i >= b; i--)
#define PQ priority_queue<int> pq;
#define MPQ priority_queue<pi, vector<int>, greater<pi>> mpq;
#define io                        \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);

int main()
{
    io;

    int n;
    cin >> n;
    int in[n];
    loop(i, 0, n)
            cin >>
        in[i];
    int ans = 0;
    loop(i, 0, n)
    {
        int cur1 = in[i];
        loop(j, i + 1, n)
        {
            int cur2 = in[j];
            if (cur2 == cur1)
                continue;
            loop(k, j + 1, n)
            {
                int cur3 = in[k];
                if (cur3 == cur2 || cur3 == cur1)
                    continue;
                if (cur1 + cur2 > cur3 && cur2 + cur3 > cur1 && cur3 + cur1 > cur2)
                    ans++;
            }
        }
    }
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 3656
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	nextReader = newScanner()
	h, a := nextInt(), nextInt()
	fmt.Println(h/a + min(h%a, 1))
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// ---------------------------------------------------------------
// I/O
// ---------------------------------------------------------------
var nextReader func() string

func newScanner() func() string {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, 1024), int(1e11))
	sc.Split(bufio.ScanWords)
	return func() string {
		sc.Scan()
		return sc.Text()
	}
}

func nextString() string { return nextReader() }

func nextInt() int { n, _ := strconv.Atoi(nextReader()); return n }

func nextInts(size int) []int {
	ns := make([]int, size)
	for i := 0; i < size; i++ {
		ns[i] = nextInt()
	}
	return ns
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main()
{
    int N, K, a; cin >> N >> K;
    vector<int> B(N);
    rep(i, N)
    {
        cin >> a;
        B[a - 1]++;
    }

    vector<int> v;
    for(auto p : B) v.push_back(p);
    sort(v.begin(), v.end());
    int d = v.size();
    if (d <= K)
        cout << 0 << endl;
    else
    {
        int ans = 0;
        rep(i, d - K)
        {
            ans += v[i];
        }
        cout << ans << endl;
    }
}

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

int main() {
  int n;
  cin >> n;
  vector<int>sum(100000+2,0);
  for(int i = 0;i < n;i++){
    int a;
    cin >> a;
    if(a == 0){
      sum[0]++;
      sum[1]++;
    }
    else{
      sum[a-1]++;
      sum[a]++;
      sum[a+1]++;
    }
  }
  int ans = sum[0];
  for(int i = 1;i <= 100000;i++){
    if(sum[i] > ans) ans = sum[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> v;
int main(){
	
	//code
	cin>>n;
	v.resize(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	int lookup=1, breakup=0;
	for(int i=0;i<n;i++){
		if(v[i]==lookup){
			lookup++;
		}
		else
			breakup++;
	}
	if(breakup==n)	cout<<"-1"<<endl;
	else	cout<<breakup<<endl;
	//code
	
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int min = Integer.MAX_VALUE;
        int res = 0;
        for(int i = 0; i < N; i++) {
            int P = sc.nextInt();
            if(P <= min) {
                res++;
                min = P;
            }
        }
        System.out.println(res);
    }
}


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

using namespace std;

#define INF (1 << 30)
#define EPS 1e-10
#define MOD 1000000007

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

using ll = long long;

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

template <typename X>
struct SegmentTree {
    using FX = function<X(X, X)>;
    int n;
    FX fx;
    const X ex;
    vector<X> dat;
    SegmentTree(int n_, FX fx_, X ex_) : fx(fx_), ex(ex_) {
        int x = 1;
        while (n_ > x) x *= 2;
        n = x;
        dat.resize(n * 2, ex);
    }

    X get(int i) {
        return dat[i + n - 1];
    }
    void set(int i, X x) {
        dat[i + n - 1] = x;
    }
    void build() {
        for (int i = n - 2; i >= 0; --i) {
            dat[i] = fx(dat[2 * i + 1], dat[2 * i + 2]);
        }
    }
    void update(int i, X x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }

    X query(int a, int b) {
        return query_sub(a, b, 0, 0, n);
    }
    X query_sub(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return ex;
        }
        else if (a <= l && r <= b) {
            return dat[k];
        }
        else {
            X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(vl, vr);
        }
    }
};

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

    vector<int> c(n);
    list<int> v[n + 1];
    auto fx = [](int x1, int x2) -> int { return x1 + x2; };
    SegmentTree<int> rsq(n, fx, 0);
    
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
        if (v[c[i]].size() == 0) {
            rsq.set(i, 1);
        }
        v[c[i]].push_back(i);
    }
    rsq.build();

    map<pair<int, int>, int> mp;
    vector<pair<int, int>> lr(q), lrs(q);
    for (int i = 0; i < q; ++i) {
        cin >> lr[i].first >> lr[i].second;
        lrs[i] = lr[i];
    }
    sort(all(lrs));
    int bl = 0;
    for (int i = 0; i < q; ++i) {
        for (int j = bl; j < lrs[i].first - 1; ++j) {
            v[c[j]].pop_front();
            if (v[c[j]].size() > 0)
                rsq.update(*v[c[j]].begin(), 1);
        }
        bl = lrs[i].first - 1;
        mp[lrs[i]] = rsq.query(lrs[i].first - 1, lrs[i].second);
    }

    for (int i = 0; i < q; ++i) {
        cout << mp[lr[i]] << endl;
    }   

    return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  vector<int> d;
  for(int i = 0;i < N; i++){
    int di;
  	cin >> di;
    d.push_back(di);
  }
  
  int ans = 0;
  
  for(int i = 0;i < N; i++){
    for(int j = i + 1;j < N; j++){
    	ans += d.at(i) * d.at(j);
    }
  }


  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

class S{
public:
  int j, o, i;
};

int h, w;
char data[1000][1000];
S dp[1000][1000];

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

  cin >> n;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> data[i][j];
    }
  }
  dp[0][0].j = 0;
  dp[0][0].o = 0;
  dp[0][0].i = 0;
  if(data[0][0] == 'J') dp[0][0].j++;
  if(data[0][0] == 'O') dp[0][0].o++;
  if(data[0][0] == 'I') dp[0][0].i++;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(i == 0 && j == 0) continue;
      if(i == 0){
        dp[i][j] = dp[i][j-1];
      }else if(j == 0){
        dp[i][j] = dp[i-1][j];
      }else{
        dp[i][j].j = dp[i-1][j].j + dp[i][j-1].j - dp[i-1][j-1].j;
        dp[i][j].o = dp[i-1][j].o + dp[i][j-1].o - dp[i-1][j-1].o;
        dp[i][j].i = dp[i-1][j].i + dp[i][j-1].i - dp[i-1][j-1].i;
      }
      if(data[i][j] == 'J') dp[i][j].j++;
      if(data[i][j] == 'O') dp[i][j].o++;
      if(data[i][j] == 'I') dp[i][j].i++;
    }
  }
  for(int i=0;i<n;i++){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    --a;--b;--c;--d;
    if(a == 0 && b == 0){
      cout << dp[c][d].j << ' ' << dp[c][d].o << ' ' << dp[c][d].i << endl;
    }else if(a == 0){
      cout << dp[c][d].j-dp[c][b-1].j << ' ' << dp[c][d].o-dp[c][b-1].o << ' ' << dp[c][d].i-dp[c][b-1].i << endl;
    }else if(b == 0){
      cout << dp[c][d].j-dp[a-1][d].j << ' ' << dp[c][d].o-dp[a-1][d].o << ' ' << dp[c][d].i-dp[a-1][d].i << endl;
    }else{
      int ans1 = dp[c][d].j - dp[c][b-1].j - dp[a-1][d].j + dp[a-1][b-1].j;
      int ans2 = dp[c][d].o - dp[c][b-1].o - dp[a-1][d].o + dp[a-1][b-1].o;
      int ans3 = dp[c][d].i - dp[c][b-1].i - dp[a-1][d].i + dp[a-1][b-1].i;
      cout << ans1 << ' ' << ans2 << ' ' << ans3 << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 13000
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> P;
 
const int inf = 1e9 + 9;
 
struct edge {
  int to, cost;
};
 
int n, r;
vector<edge> G[1550];
vector<int> V[1550];
//vector<int> L;

int d[1550];
bool f[1550], L[1550];
 
void path(int u)
{
  L[u] = true;
  //L.push_back(u);
  if (d[u] == 0) return;
  for (int i = 0; i < V[u].size(); i++){
    path(V[u][i]);
  }
}
 
int main()
{
  cin >> n >> r;
  for (int i = 0; i < r; i++){
    int s, t, d;
    cin >> s >> t >> d;
    s--; t--;
    edge e;
    e.to = t; e.cost = d;
    G[s].push_back(e);
    e.to = s;
    G[t].push_back(e);
  }
 
  priority_queue<P, vector<P>, greater<P>> q;
 
  int max_d = 0;
  for (int i = 0; i < n; i++){
    q.push(P(0, i));
    fill(d, d + n, inf);
    d[i] = 0;
 
    vector<int> E;
    int max_c = 0;
 
    while (!q.empty()){
      P p = q.top(); q.pop();
      int v = p.second;
      if (d[v] < p.first) continue;
      for (int j = 0; j < G[v].size(); j++){
        edge e = G[v][j];
 
        if (d[e.to] == d[v] + e.cost){
          V[e.to].push_back(v);
          q.push(P(d[e.to], e.to));
        }
        if (d[e.to] > d[v] + e.cost){
          d[e.to] = d[v] + e.cost;
          V[e.to].clear();
          V[e.to].push_back(v);
          q.push(P(d[e.to], e.to));
        }
      }
    }
 
    E.clear();
    for (int j = 0; j < n; j++){
      if (d[j] == max_c) {
        E.push_back(j);
      }
      if (d[j] > max_c){
        max_c = d[j];
        E.clear();
        E.push_back(j);
      }
    }
 
    if (max_c == max_d){
      for (int j = 0; j < E.size(); j++){
        path(E[j]);
      }
    }
    if (max_d < max_c){
      //L.clear();
      memset(L, false, sizeof(L));
      max_d = max_c;
      for (int j = 0; j < E.size(); j++){
        path(E[j]);
      }
    }
  }

  //sort(L.begin(), L.end());
  //L.erase(unique(L.begin(), L.end()), L.end());
  /*
  for (int i = 0; i < L.size(); i++){
    f[i] = true;
  }
  */
 
  vector<int> p;
  for (int i = 0; i < n; i++){
    if (!L[i]) p.push_back(i + 1);
  }

  cout << p.size() << endl;
  for (int i = 0; i < p.size(); i++){
    cout << p[i] << endl;
  }
}

Measured memory_bytes: 3420
n,m = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b])
    
ab.sort()
cnt = 0
ans = 0
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    if cnt +b >= m:
        ans += (m-cnt)*a
        break
    else:
        ans +=a*b
        cnt +=b
print(ans)

Measured memory_bytes: 20048
#include <iostream>
#include <math.h>
using namespace std;
int N,D;
#define rep(i,N) for(int i=0;i<N;i++)
int X[11][11];
int main(){
    cin >> N >> D;
    rep(i,N){
        rep(j,D){
            cin >> X[i][j];
        }
    }
    int count = 0;
    for(int i=0;i<N-1;i++){
        for(int j=i+1;j<N;j++){
            double sum = 0;
            for(int k=0;k<D;k++){
                sum += pow(X[i][k]-X[j][k],2);
            }
            if(sqrt(sum)==(int)sqrt(sum)){
                count++;
        }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int q,x,M,i,vis[N],j;
long long s[N],n,ans;
int main()
{
	scanf("%lld %d %d",&n,&x,&M);
	s[1]=x;
	vis[x]=1;
	for(i=2;i<=n;++i)
	{
		s[i]=s[i-1]*s[i-1]%M;
		if(vis[s[i]])
			break;
		vis[s[i]]=i;
	}
	if(i>n)
	{
		for(i=1;i<=n;++i)
			ans+=s[i];
		cout<<ans;
	}
	else
	{
		for(j=1;j<=vis[s[i]];++j)
			ans+=s[j];
		long long m=0;
		for(j=vis[s[i]]+1;j<=i;++j)
			m+=s[j];
		n-=vis[s[i]];
		for(j=vis[s[i]]+1;j<=vis[s[i]]+n%(i-vis[s[i]]);++j)
			ans+=s[j];
		cout<<ans+m*(n/(i-vis[s[i]]));
	}
}


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

int main(){
  int n,k,h,g;
  cin >> n >> k;
  vector<int> vec(n);
  for(int i = 0;i < n;i++){
    cin >> vec.at(i);
  }
  g = 0;
  for(int j = 0;j < n;j++){
    h = vec.at(j);
    g += min(h,abs(k-h))*2;
  }
  cout << g << endl;
}


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

int main() {
  int N;
  string S;
  cin >> N >> S;
  
  int ans = 0;
  for (int i = 0; i < N - 2; i++) {
    if ((S[i] == 'A') && (S[i + 1] == 'B') && (S[i + 2] == 'C')) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

int main()
{
    std::string S, T;
    std::cin >> S >> T;

    for (size_t i = 0; i < S.size(); ++i) {
        auto U = S.substr(i) + S.substr(0, i);
        if (T == U) {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }
    std::cout << "No" << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

ll N, M;
vector<vector<ll>> to;
const ll INF = 1e18;

// svを通る最短閉路をみつける
vector<ll> bfs(ll sv){
  queue<ll> q;
  // dist[i] : svからの距離
  // pre[i] : iの直前に訪れる頂点
  vector<ll> dist(N,INF), pre(N,-1);

  dist[sv] = 0;
  q.push(sv);
  while(!q.empty()){
    ll cv = q.front();
    q.pop();
    FOREACH(nv, to[cv]){
      if(dist[nv] != INF) continue;
      pre[nv] = cv;
      dist[nv] = dist[cv] + 1;
      q.push(nv);
    }
  }

  // (閉路長，終点);
  P cycle = make_pair(INF,-1);
  REP(u,N){
    FOREACH(v,to[u]){
      //閉路発見
      if(v == sv){
        cycle = min(cycle, make_pair(dist[u], u));
      }
    }
  }

  //閉路なし
  if(cycle.first == INF) return vector<ll>(N+1);
  //閉路復元
  ll v = cycle.second;
  vector<ll> res;
  while(v != -1){
    res.push_back(v);
    v = pre[v];
  }
  return res;
}

int main(){
  cin >> N >> M;
  to.resize(N);
  REP(i,M){
    ll a,b; cin >> a >> b;
    a--; b--;
    to[a].push_back(b);
  }

  //始点を全探索し，最短閉路を見つける
  vector<ll> ans(N+1);
  REP(i,N){
    vector<ll> now = bfs(i);
    if(SZ(now) < SZ(ans)) ans = now;
  }
  //閉路なし
  ll K = SZ(ans);
  if(K == N+1){
    cout << -1 << endl;
    return 0;
  }
  //最短閉路をなす頂点を出力
  cout << K << endl;
  REP(i,K){
    cout << ans[i] + 1 << endl;
  }
}

Measured memory_bytes: 384
#include<stdio.h>
#include<math.h>
typedef long long ll;
int main()
{
	ll n, rt, i;
	scanf("%lld", &n);
	rt = sqrt(n);
	for(i = rt; i >= 1; --i)
	  if(n%i == 0)
	    break;
	printf("%lld", i + n/i - 2);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
  int k,x;
  cin >> k >> x;
  int minn = x-k+1;
  int maxx = x+k-1;
  for (int i = minn; i <= maxx; ++i) {
    cout << i << ' ';
  }
    cout << endl;
}


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

int main()
{
    int cup[3] = {1,0,0};
    char a,b,r;
    while (scanf(" %c,%c",&a,&b) != EOF)
    {
	swap(cup[int(a-'A')],cup[int(b-'A')]);
    }
    for (int i=0; i<3; i++)
    {
	if (cup[i] == 1)
	{
	    r = 'A' + i;
	    break;
	}
    }
    cout << r << endl;
}

Measured memory_bytes: 0