akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int           long long
#define	pb            push_back
#define all(a)        (a).begin(),(a).end()
#define sz(x)         (int)x.size()
#define F             first
#define S             second
#define endl          "\n"
#define inf           1000000007
#define FOR(i, a, b)  for(int i=a; i<b; i++)
#define bigboi        1e18
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers. 

void solve(){	
	string s, t;
	cin>>s>>t;
	int n = sz(s), m = sz(t);
	int dp[3002][3002] = {{0}};	
	dp[0][0] = 0;
	FOR(i, 1, n+1){
		FOR(j, 1, m+1){
			if(s[i-1]==t[j-1]){
				dp[i][j] = dp[i-1][j-1]+1;
			}
			else{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	//cout<<dp[n][m]<<endl;

	int i=n, j=m;
	string lcs="";
	while(i && j){
		if(s[i-1] == t[j-1]){
			lcs+=s[i-1];
			i--, j--;
		}
		else if(dp[i-1][j]>dp[i][j-1]){
			i--;
		}
		else{
			j--;
		}
	}
	reverse(all(lcs));
	cout<<lcs<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 	
	int t=1;
	//cin>>t;
	FOR(i, 1, t+1){	
		//cout<<"Case #"<<i<<": ";
		solve();
	}
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
 
}


Measured memory_bytes: 70656
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main()
{
  int d, g;
  cin >> d >> g;

  vector<pair<int, int>> problem;
  for (int i = 0; i < d; i++) {
	pair<int, int> tmp;
	cin >> tmp.first >> tmp.second;
	problem.push_back(tmp);
  }
  
  int res = 1e9;
  for (int i = 0; i < 1 << d; i++) {
	int solve = 0;
	int score = 0;
	int incom_high_score = -1;
	for (int j = 0; j < d; j++) {
	  if ((i >> j & 1) == 1) {
		score += 100 * (j + 1) * problem[j].first + problem[j].second;
		solve += problem[j].first;
	  } else {
		incom_high_score = j;
	  }
	} /* end of j loop */
	if (score < g) {
	  int s1 = 100 * (incom_high_score + 1);
	  int need = (g - score + s1 - 1) / s1;
	  if (need >= problem[incom_high_score].first) {
		continue;
	  }
	  solve += need;
	}
	res = min(res, solve);
  } /* end of i loop */

  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
class BIT{
public:
  int n,bit[555555];
  BIT(){fill(bit,bit+555555,0);}
  void add(int i,int x){
    while(i<=n){
      bit[i]+=x;
      i+=i&-i;
    }
  }
  int sum(int i){
    int s=0;
    while(i>0){
      s+=bit[i];
      i-=i&-i;
    }
    return s;
  }
};
BIT b=BIT(),t=BIT();
void Main() {
  b.n=t.n=200001;
  ll n;
  R n;
  P a[n];
  rep(i,n) cin >> a[i].F >> a[i].S;
  ll d[111111];
  mem(d);
  rep(i,n) {
    d[a[i].F]++;
    d[a[i].S]--;
    b.add(a[i].F,1);
    t.add(a[i].S,1);
  }
  rep(i,100000) d[i+1]+=d[i];
  ll M2=0,M=0;
  rep(i,100001) M2=max(M2,d[i]);
  rep(i,n) {
    ll x=b.sum(a[i].S-1);
    ll y=t.sum(a[i].F);
    M=max(M,x-y);
  }
  pr(M,M2);
  
}

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


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

void showArray(int x[], int n){
	for (int i = 0; i < n; i++) {
		cout << x[i];
		if (i != n-1)	cout << " ";
	}
	cout << endl;
}

int main(){
	int n, v, i, j;
	int a[100];
	cin >> n;
	for (i = 0; i < n; i++)	cin >> a[i];
	showArray(a, n); 
	for (i = 1; i < n; i++) {
		v = a[i];
		j = i-1;
		while (j >= 0 && v < a[j]) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = v;
		showArray(a, n);
	}
	return 0;
}

Measured memory_bytes: 1160
/**
*    author:  yuya1234
*    created: 30.06.2020 17:11:36
**/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define FORV(i,v) for(auto i=v.begin(); i!=v.end();i++)

#define ALL(v) (s).begin(), (s).end()
#define SORT(s) sort((s).begin(),(s).end())
#define SORTD(s) sort((s).rbegin(),(s).rend())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define SZ(x) ((int)(x).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))

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

    int k,s;
    cin>>k>>s;

    int ans=0;
    REP(i,k+1)
    {
        REP(j,k+1)
        {
            if(0<=s-(i+j) && s-(i+j)<=k)ans++;
        }
    }

    cout<<ans<<endl;

    return 0;
}

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

namespace ABC141B
{
    class Program
    {
        static void Main(string[] args)
        {
            string kisuu = "RLD";
            string guusuu = "LUD";

            var S = Console.ReadLine();

            bool ans = true;
            for (int i = 0; i < S.Length; i++)
            {
                if (i % 2 == 0)
                {
                    //奇数
                    if (S[i] == 'R' || S[i] == 'U' || S[i] == 'D') continue;
                    else ans = false;
                }
                else
                {
                    if (S[i] == 'L' || S[i] == 'U' || S[i] == 'D') continue;
                    else ans = false;
                }

            }

            if (ans) Console.WriteLine("Yes");
            else Console.WriteLine("No");

            Console.ReadKey();
        }

        static int[] ReadInt()
        {
            int[] ret = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return ret;
        }
        static long[] ReadLong()
        {
            long[] ret = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return ret;
        }
    }
}


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

using uli = unsigned long int;
using lli = long long int;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define repa(a,i,x) for(int i=a;i<=x;i++)

int main(){	
	string S;
	cin >> S;
	
	if(S[2]==S[3] && S[4]==S[5])cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

using namespace std;

typedef long long ll;

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

  if(n * 2 >= m)
  {
	cout << m / 2 << endl;
  }
  else
  {
	cout << n + (m - 2 * n) / 4 << endl;
  }
}


Measured memory_bytes: 256
import Foundation

func check(t: [[Int]], d: [Bool], x: Int) -> Bool {
  var rst = [Int](repeating: 0, count: t[0].count)
  for i in 0..<t.count {
    if !d[i] { continue }
    for j in 0..<t[i].count {
      rst[j] += t[i][j]
    }
  }
  let ans = rst.contains { x > $0 }
  return !ans
}

func calc(c: [Int], d: [Bool]) -> Int {
  return c.enumerated().reduce(0) { (a, e) in
    return d[e.0] ? a + c[e.0] : a
  }
}

if let s = readLine() {
  let ss = s.split(separator: " ").map { Int($0)! }
  let n = ss[0] // 参考書数
  let m = ss[1] // アルゴリズム数
  let x = ss[2] // 目標理解度
  var c = [Int](repeating: 0, count: n)
  var a = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
  for i in 0..<n {
    if let aa = readLine() {
      let t = aa.split(separator: " ").map { Int($0)! }
      c[i] = t[0]
      for j in 1..<m+1 {
        a[i][j-1] = t[j]
      }
    }
  }
  
  let max: Int = Int(truncating: NSDecimalNumber(decimal: pow(2, n)))
  var ans = [Int](repeating: Int.max, count: max)
  for i in 0..<max {
    var b = String(i, radix: 2)
    for _ in 0..<n-b.count {
      b = "0" + b
    }
    let d = b.enumerated().map { $1 == "1" }
    if check(t: a, d: d, x: x) {
      ans.append(calc(c: c, d: d))
    }
  }
  
  if let min = ans.min() {
    if min == Int.max {
      print("-1")
    } else {
      print(min)
    }
  }
}


Measured memory_bytes: 13860
#include<iostream>
#include<cstdio>
using namespace std;
long long s1[200010],s2[200010];
int n,m;
long long all;
int nw;
long long ans=1e18;
int main()
{
	scanf("%d%d%d",&n,&m,&nw);
	nw--;
	for(int i=1;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		x--;
		nw%=m;
		if(x<nw)x+=m;
		all+=x-nw;
		s1[nw+1]++;
		s1[x+1]--;
		s2[nw+1]+=nw;
		s2[x+1]-=nw;
		nw=x;
	}
	for(int i=1;i<2*m;i++)
	{
		s1[i]+=s1[i-1];
		s2[i]+=s2[i-1];
	}
	for(int i=0;i<m;i++)
	{
		long long a=s1[i],b=s2[i];
		long long t=all;
		t-=(long long)i*a-b-a;
		a=s1[i+m],b=s2[i+m];
		t-=(long long)(i+m)*a-b-a;
		ans=min(ans,t);
	}
	printf("%lld",ans);
	return 0;
} 

Measured memory_bytes: 3328
//Bismillahir-Rahmanir-Rahim
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int llu;
#define f1(i,n) for(i=1;i<=n;i++)
#define f(i,n) for(i=0;i<n;i++)
#define Max 100009
#define Mx 1e10
#define pb push_back
#define mp make_pair
using namespace std;
int main()
{
    	ll n,mn=0,mx=0,x,i,t=0,j=0,k=0;
    	set<ll>s;
    	cin>>n;
    	ll a[n],c[n],g[n];
    	f(i,n)
    	{
    	    cin>>a[i];
    	}
        sort(a,a+n);
        for(i=n-1;i>=0;i--)
        {
            if(a[i]==a[i-1]&&a[i-1]==a[i-2]&&a[i-2]==a[i-3])
            {
                t=max(t,a[i]*a[i]);
            }
            else if(a[i]==a[i-1]&&mx==0)
            {
                mx=a[i];
            }
            else if(a[i]==a[i-1]&&mx!=a[i]&&a[i]>mn)
            {
                mn=a[i];
            }
            if(mx>0&&mn>0)
                k=max(k,mx*mn);
        }
         cout<<max(k,t)<<endl;
}






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

int main(){
    string s;
    cin >> s;
    int a,b,c,d;
    a=s.at(0)-'0';
    b=s.at(1)-'0';
    c=s.at(2)-'0';
    d=s.at(3)-'0';
    if(a+b+c+d == 7){
        cout<<a<<"+"<<b<<"+"<<c<<"+"<<d<<"=7"<<endl;
        return 0;
    }
    if(a+b+c-d == 7){
        cout<<a<<"+"<<b<<"+"<<c<<"-"<<d<<"=7"<<endl;
        return 0;
    }
    if(a+b-c+d == 7){
        cout<<a<<"+"<<b<<"-"<<c<<"+"<<d<<"=7"<<endl;
        return 0;
    }
    if(a-b+c+d == 7){
        cout<<a<<"-"<<b<<"+"<<c<<"+"<<d<<"=7"<<endl;
        return 0;
    }
    if(a-b-c+d == 7){
        cout<<a<<"-"<<b<<"-"<<c<<"+"<<d<<"=7"<<endl;
        return 0;
    }
    if(a-b+c-d == 7){
        cout<<a<<"-"<<b<<"+"<<c<<"-"<<d<<"=7"<<endl;
        return 0;
    }
    if(a+b-c-d == 7){
        cout<<a<<"+"<<b<<"-"<<c<<"-"<<d<<"=7"<<endl;
        return 0;
    }
    if(a-b-c-d == 7){
        cout<<a<<"-"<<b<<"-"<<c<<"-"<<d<<"=7"<<endl;
        return 0;
    }
}

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

public class Main {
	private static void solve(){
	//Implement solution here.
		int n = ni();
		int max = 0;
		int result = 0;
		for(int i = 0; i < n; i++) {
			int h = ni();
			if(h >= max) {
				result++;
				max = h;
			}
		}
		System.out.println(result);
	}

    //Switch input source (stdin/file)
	private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args){
        String debugDataPath = System.getenv("DD_PATH");        
        if(debugDataPath != null){
            try{
            	br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
            }catch(Exception e){
                throw new RuntimeException(e);
            }
        }
        solve();
	}

    //Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
    //Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
    //Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
    //Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
    //Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
    //Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

Measured memory_bytes: 21332
#include <iostream>
#include<array>
#include<algorithm>
using namespace std;
int main() {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	int max = 0;
	if (3*a[2] % 2 == (a[0]+a[1]+a[2])%2) {
		 max = a[2];
	}
	else {
		max = a[2] + 1;
	}
	int ans = 0;
	for (int i = 0; i < 3; i++) {
		ans += max - a[i];
	}
	cout << ans/2 << endl;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner scanner=new Scanner(System.in);

		int n=scanner.nextInt();



		List<Integer> data=new ArrayList<Integer>();

		for(int i=0;i<n;i++) {

			int buf=scanner.nextInt();

			if(!data.contains(buf)) {
				data.add(buf);
			}

		}

		int result=data.size();






		System.out.println(result);



		scanner.close();

	}

	public static int getsumofkakuketa(int n) {

		int result=0;

		while(true) {

			result+=n%10;

			if(n/10!=0) {
				n/=10;
			}else {
				return result;
			}
		}



	}

	public static boolean isMacthed(int a,int b,int sum) {

		if(sum>=a && sum<=b) {
			return true;
		}else {
			return false;
		}

	}



}







Measured memory_bytes: 21844
function Main(input){
    let s = (input.split("\n")[0]).split("");
    let t = (input.split("\n")[1]).split("");
    let ans = t.length ;
    for(let a = 0; a <= s.length - t.length; a++){
        let diff = 0;
        for(let b = 0; b < t.length; b++){
            if(t[b] != s[a+b]){
                diff++;
            }
        }
        ans = Math.min(diff, ans);
    }
    console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 32496
#include <iostream>
using namespace std;
int main () {
	int a, b, c, t;

	cin >> a >> b >> c;

	if ( ((a >= 1) && (a <= 10000)) && ((b >= 1) && (b <= 10000)) && ((b >= 1) && (b <= 10000))) {
		if (a > b) {
			t = a;
			a = b;
			b = t;
		}
		if (b > c) {
			t = b;
			b = c;
			c = t;
		}
		if (a > b) {
			t = a;
			a = b;
			b = t;
		}
	} else {
		cout << "Input number is invalid.\n";
	}
	cout << a << " " << b << " " << c << "\n";
	return 0;
}

Measured memory_bytes: 1164
from collections import deque


def bfs(root):
    Q = deque()
    distance[root] = 0
    Q.append(root)
    i = root
    while len(Q) > 0:
        i = Q.popleft()
        for v in range(n):
            if adjMat[i][v] == 1 and color[v] == 'white':
                Q.append(v)
                color[v] = 'gray'
                distance[v] = distance[i] + 1
        color[i] = 'black'


n = int(input())
adjMat = [[0] * n for _ in range(n)]
color = ['white'] * n
distance = [-1] * n

for _ in range(n):
    adj = list(map(int, input().split()))
    i = adj[0]
    v = adj[2:]
    for j in v:
        adjMat[i - 1][j - 1] = 1

bfs(0)

for i in range(n):
    out = ''
    out += '{} {}'.format(i + 1, distance[i])
    print(out)

Measured memory_bytes: 8052
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
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);}



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

    ll n,t; cin >> n >> t;
    vector<ll> h(n); for(auto& in:h) cin >> in;
    ll startt = 0,waitt = 0;
    for(int i = 0; i < n;i++){
        waitt = max(waitt,h[i]);
        
        ll t1 = (t - startt) / waitt;
        ll t2 = (t - startt) % waitt;
        
        cout << max(1LL,(t1 + (t2 >= h[i]) + 1)) << endl;
        startt += h[i];
    }
    return 0;
}



Measured memory_bytes: 3624
from collections import deque
import sys

N,K = map(int,input().split())
A = list(map(int,input().split()))

# ループを見るける
target = deque()
target_s = set()
target.append(1)
target_n = A[0]
for i in range(K):
    before = len(target_s)
    target_s.add(target_n)
    if len(target_s) != before:
        target.append(target_n)
        # target_s.add(target_n)
        target_n = A[target_n-1]
    else:
        if target[-1] != 1:
            target.append(target_n)
        t = target.pop()
        t = target.index(t)
        if t != 0:
            K -= len(target)
        K = K%(len(target) - t)
        print(target[K+t])
        sys.exit()

print(target[-1])



Measured memory_bytes: 33808
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
const ll inf=1e9+7;
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; }

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

    char s[h+2][w+2];
    rep(i,1,h+1)
    rep(j,1,w+1) cin>>s[i][j];

    rep(i,0,w+2) s[0][i]='.',s[h+1][i]='.';
    rep(i,1,h+1) s[i][0]='.',s[i][w+1]='.';


    rep(i,1,h+1){
      rep(j,1,w+1){
        int tmp=0;
        if(s[i][j]=='#') cout<<'#';
        else{
          rep(k,-1,2)
          rep(l,-1,2){
            if(s[i+k][j+l]=='#') tmp++;
          }

          cout<<tmp;
        }
      }
      cout<<endl;
    }



/*    rep(i,0,h+2){
      rep(j,0,w+2) cout<<s[i][j];

      cout<<endl;
    }
*/
}


Measured memory_bytes: 256
// atcoder/agc029/B/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

constexpr array<int, 8> di({0, 1, -1, 0, 1, -1, 1, -1});
constexpr array<int, 8> dj({1, 0, 0, -1, 1, -1, -1, 1});
constexpr lli mod = 1e9 + 7;

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.setf(ios_base::fixed);
  cout.precision(15);

  int n;
  while (cin >> n) {
    vec<int> a(n);
    cin >> a;
    sort(a.begin(), a.end());
    map<int, int> m;
    each (i, a) ++m[i];
    reverse(a.begin(), a.end());
    int cnt = 0;
    each (i, a) {
      if (!m.count(i)) continue;
      if (--m[i] == 0) m.erase(i);
      for (int j = 31; 0 <= j; --j) {
        lli x = (1LL << j) - i;
        if (m.count(x)) {
          if (--m[x] == 0) m.erase(x);
          ++cnt;
          break;
        }
      }
    }
    cout << cnt << endl;
  }

  return 0;
}


Measured memory_bytes: 10368
#include <iostream>
#include <set>

using namespace std;

int main()
{
  set<int> a;
  int s;
  cin >> s;
  int m=1;

  while(true)
    {
      decltype(a)::iterator it = a.find(s);
      if (it != a.end()) {
	int value = *it;
	cout << m << endl;
	break;
      }
      a.insert(s);
      if( s%2 == 0 )
	s /= 2;
      else
	s = 3*s+1;	    
      m++;
    }
  return 0;
}


Measured memory_bytes: 256
a = input()
b = input()
c = input()

def match(c1, c2):
    return c1 == '?' or c2 == '?' or c1 == c2

M = 2000

ab, ac, bc = [], [], []
ab_append = ab.append
ac_append = ac.append
bc_append = bc.append

for _  in range(10000):
    ab_append(0)
    ac_append(0)
    bc_append(0)

for _  in range(10000):
    bc_append(0)

A, B, C = len(a), len(b), len(c)
for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+5000] = 1
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i-j+5000] = 1
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+10000] = 1

ans = 3 * M

for i in range(-2*M, 2*M):
    for j in range(-2*M, 2* M):
        if ab[i+5000] == 0 and ac[j+5000] == 0 and bc[j-i+10000] == 0:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R - L)

print(ans)


Measured memory_bytes: 55296
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 = input()
print("Yes" if N == N[::-1] else "No")



Measured memory_bytes: 5400
//long time no ac
#include <bits/stdc++.h>
using namespace std;
 
#define 	ll				long long
#define 	vii				vector<int>
#define		rep(i,n) 		for(i=0;i<n;i++)
#define		repe(i,I1,I2) 	for(i=I1;i<I2;i++)
#define		INF  			1e9 + 7
#define		pb  			push_back
#define		mp  			make_pair
#define		endl			'\n'
#define 	mod				1000000007
 
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,k,t,c=0,i,a,b;
	t=1;
	//cin>>t;
	
	while(t--)
	{
		cin>>n;
	if(n==1)
        {
          cout<<"Hello World";
        }
        else
        {
        	cin>>a>>b;
          cout<<a+b;
        }
		if(t!=0)
	   		cout<<"\n";
	}
	return 0;
}

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

typedef long long LL;
LL dp[105][100005];

LL knap(int wt[],int val[],int n,int W){
  if(W<0) return -99999999999999999;
  if(W==0 || n<0) return 0;
  if(dp[n][W]!=-1) return dp[n][W];
  dp[n][W] = max(knap(wt,val,n-1,W-wt[n])+val[n],knap(wt,val,n-1,W));
  return dp[n][W];
}

int main(){
	int n,W;
  	cin>>n>>W;
  	int w[105],v[105];
  	for(int i=0;i<n;i++) cin>>w[i]>>v[i];
  	for(int i=0;i<n;i++){
    	for(int j=0;j<=W;j++){
        	dp[i][j] = -1;
        }
    }
  	cout<<knap(w,v,n-1,W);
}

Measured memory_bytes: 81676
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX_N=10e5;
int a[MAX_N],b[MAX_N-1];
int main(void)
{
	int N,M;
		cin >> N >> M;
	for(int i=0;i<M;i++)
		cin >> a[i];
	sort(a,a+M);
	for(int i=0;i<M-1;i++){
		b[i]=a[i+1]-a[i];
	}
	sort(b,b+M-1);
	int ans=0;
	for(int i=0;i<M-1-N+1;i++)
		ans+=b[i];
	cout  << ans << endl;
	return 0;
}

Measured memory_bytes: 4736
import java.util.*;
 
public class Main{
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         for(;;){
            int n = sc.nextInt();
            if(n==0) break;
            int cnt = 0;
            int flag = -1;
            for(int i=0;i<n;i++){
                int k = sc.nextInt();
                if(k>0) cnt++; 
                if(k>=2) flag = 1; 
            }
            if(flag<0) System.out.println("NA");
            else System.out.println(cnt+1);
        }
    }
}

Measured memory_bytes: 158436
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
	ll N, A, B;
	cin >> N >> A >> B;
	ll q=N/(A+B), r=N%(A+B);
	cout << A*q+min(A, r) << endl;
	return 0;
}

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

#define int long long
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
using namespace std;

int32_t main() {
	fastio;

	int n;
	cin >> n;
	set<string> s;
	int count = 0;
	while(n--) {
		string x;
		cin >> x;
		if(s.find(x) == s.end()) {
			s.insert(x);
			++count;
		}
	}
	cout << count;

	return 0;
}


Measured memory_bytes: 19216
#include <bits/stdc++.h>
using namespace std;
const int N=100009;
int dp[N][4],ar[N][4];
int n;
void init(){
	for(int i=0; i<=n; i++){
		dp[i][1]=-1;
		dp[i][2]=-1;
		dp[i][3]=-1;
	}

}
int go(int day,int id)
{
	if(dp[day][id]!=-1) return dp[day][id];

	int a,b;
	if(id==1) a=go(day+1,2)+ar[day][1],b=go(day+1,3)+ar[day][1];
	if(id==2) a=go(day+1,1)+ar[day][2],b=go(day+1,3)+ar[day][2];
	if(id==3) a=go(day+1,1)+ar[day][3],b=go(day+1,2)+ar[day][3];

	return dp[day][id]=max(a,b);
}
int main()
{
  int i;
  scanf("%d",&n);
  init();
  for(i=1; i<=n; i++){
	scanf("%d %d %d",&ar[i][1],&ar[i][2],&ar[i][3]);
  }
  dp[n][1]=ar[n][1];
  dp[n][2]=ar[n][2];
  dp[n][3]=ar[n][3];

  int a=go(1,1);
  int b=go(1,2);
  int c=go(1,3);

  a=max(a,b);
  a=max(a,c);

  printf("%d\n",a);
}

Measured memory_bytes: 11508
#include <iostream>
#include <math.h>
using namespace std;
int main(void){
     long k,a,b;
     k=0;
     a=0;
     b=0;
     cin >> k >> a >> b;
    if(k>a&&a+2<b){
        if(k==a+1){
            cout << dec << b <<endl;
        }else if(fmod(k-a-1,2)==0){
            int c = (k-a-1)/2;
            cout << dec << c*(b-a)+b<<endl;
        }else if(fmod(k-a-1,2)!=0){
            int d = (k-a-1)/2;
            cout << dec << d*(b-a)+b+1<<endl;
        }else{
        }
    }else{
        cout << dec << k+1 <<endl;
    }
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int read()
{
	int 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 n,m;
int tot[30];
int main()
{
	n=read(),m=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			char ch=getchar();
			while (ch<'a'||ch>'z') ch=getchar();
			++tot[ch-'a'+1];
		}
	if (n==1||m==1)
	{
		if (n%2==1&&m%2==1)
		{
			int r=0;
			for (int i=1;i<=26;i++)
				if (tot[i]%2==1) ++r;
			if (r>1) cout << "No" << endl; else cout << "Yes" << endl;
		}
		else
		{
			int r=0;
			for (int i=1;i<=26;i++)
				if (tot[i]%2==1) ++r;
			if (r>0) cout << "No" << endl; else cout << "Yes" << endl;
		}
	} else
	{
		int r=0;
		if (n%2==1) r+=m/2;
		if (m%2==1) r+=n/2;
		int t=0;
		if (n%2==1&&m%2==1) t=1;
		bool check=true;
		for (int i=1;i<=26;i++) if (tot[i]%2==1) {--t,--tot[i];}
		if (t!=0) check=false;
		for (int i=1;i<=26;i++) if (tot[i]%4==2) --r;
		if (r<0) check=false;
		if (check) cout << "Yes" << endl; else cout << "No" << endl;
	}
	return 0;
}


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

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

    string res = "APPROVED";
    int in;
    for (int i = 0; i < n; i++) {
        cin >> in;
        if (in % 2 == 0) {
            if (in % 3 != 0 && in % 5 != 0) res = "DENIED";
        }
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 3604
package main

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

const (
	initialBufSize = 1e4
	maxBufSize     = 1e6 + 7
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

// 解説放送より
// https://youtu.be/ENSOy8u9K9I?t=3667
// 再実装

func main() {
	N, K := nextInt(), nextInt()
	MAXD := 60
	nex := make([][]int, MAXD+1)
	for i := 0; i < MAXD+1; i++ {
		nex[i] = make([]int, N)
	}
	for i := 0; i < N; i++ {
		nex[0][i] = nextInt() - 1
	}
	for p := 0; p < MAXD; p++ {
		for r := 0; r < N; r++ {
			nex[p+1][r] = nex[p][nex[p][r]]
		}
	}
	var cur int
	for p := MAXD; p >= 0; p-- {
		if K>>p&1 == 1 {
			cur = nex[p][cur]
		}
	}
	fmt.Println(cur + 1)
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func abs(a int) int {
	if a > 0 {
		return a
	} else {
		return -a
	}
}

func pow(p, q int) int {
	res := p
	if q == 0 {
		return 1
	}
	for i := 0; i < q-1; i++ {
		res *= p
	}
	return res
}

func MinOf(vars ...int) int {
	min := vars[0]
	for _, i := range vars {
		if min > i {
			min = i
		}
	}
	return min
}

func MaxOf(vars ...int) int {
	max := vars[0]
	for _, i := range vars {
		if max < i {
			max = i
		}
	}
	return max
}

func gcdof2numbers(a int, b int) int {
	if b == 0 {
		return a
	}
	return gcdof2numbers(b, a%b)
}

func lcmof2numbers(a int, b int) int {
	return a / gcdof2numbers(a, b) * b
}

// マイナスの場合は考慮していない
func fuctorial(a int) int {
	if a == 1 || a == 0 {
		return 1
	} else {
		return fuctorial(a-1) * a
	}
}

func NextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

// 素因数分解したmapを返す
func primeFuctorize(n int) map[int]int {
	pf := map[int]int{}
	for i := 2; i*i <= n; i++ {
		for n%i == 0 {
			pf[i]++
			n /= i
		}
	}
	if n != 1 {
		pf[n]++
	}
	return pf
}


Measured memory_bytes: 102916
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<vector>
using namespace std;

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//infinity
#define INTINF 2000000000
#define LONGINF 2000000000

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

int main(){
	int n;
	cin >> n;
	int a[n];
	REP(i, n) cin >> a[i];
	sort(a, a+n);

	long long f = 0, s = 0;
	REP(i, n - 1){
		if(a[i] != a[i+1]) continue;

		if(a[i] > f){
			s = f;
			f = a[i];
			i++;
		}else if(a[i] > s){
			s = a[i];
			i++;
		}
	}
	cout << s * f << endl;
	return 0;
}


Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int n;
char s[64];
bool w[64][64];
LL f[64][64][64],g[64][64][64][64];
LL dfs2(short,short,short,short);
LL dfs1(short a,short b,short c){
	if (f[a][b][c]!=-1) return f[a][b][c];
	f[a][b][c]=0;
	if ((c-a)&1) return 0;
	if (a<c&&(a==b||b==c)) return 0;
	if (a==b&&b==c) return f[a][b][c]=1;
	for (short p=a;p<b;++p)
		for (short q=b+1;q<=c;++q)
			if (w[p][q])
				for (short i=p;i<b;++i)
					f[a][b][c]+=dfs1(a,p,i)*dfs2(i+1,b,q,c);
	return f[a][b][c];
}
LL dfs2(short a,short b,short q,short c){
	if (g[a][b][q][c]!=-1) return g[a][b][q][c];
	g[a][b][q][c]=0;
	for (short i=b+1;i<=q;++i)
		g[a][b][q][c]+=dfs1(a,b,i-1)*dfs1(i,q,c);
	return g[a][b][q][c];
}
int main()
{
	scanf("%d",&n),n<<=1;
	for (int i=1;i<=n;++i){
		scanf("%s",s);
		for (int j=1;j<=n;++j) w[i][j]=s[j-1]-'0';
	}
	memset(f,-1,sizeof(f));
	memset(g,-1,sizeof(g));
	LL ans=0;
	for (int i=2;i<=n;++i)
		if (w[1][i]) ans+=dfs1(2,i,n);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 133248
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[233][233];
int a[233][233];
int n;
int main()
{
	scanf("%d",&n);
	for(int j=1;j<=2;j++)
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i][j]);
	dp[1][1]=a[1][1];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=2;j++)
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
	printf("%d\n",max(dp[n][1],dp[n][2]));
	return 0;
}

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

int main() {
    int n, k, tmp;
    int ans = 0;
    vector<int> p;
    cin >> n >> k;
    for(int i=0; i<n; i++)
    {
        cin >> tmp;
        p.push_back(tmp);
    }
    sort(p.begin(), p.end());
    for(int i=0; i<k; i++)
    {
        ans += p[i];
    }
    cout << ans << endl;
    return 0;
}



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

int main(){
    long long N, x, p;
    cin >> N >> x >> p;
    
    long long a, A(0);
    for(long long i = 1, t; i < N; ++i){
        cin >> a;
        t = max(0LL, a + p - x);
        A += t;
        a -= t;
        p = max(0LL, a);
    }
    cout << A << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4
1 2 2 4
2 1 4
3 0
4 1 3

output:
1 0
2 1
3 2
4 1
"""

import sys
from collections import deque

UNVISITED, VISITED_IN_QUEUE, POPPED_OUT = 0, 1, 2


def graph_bfs(v_init):
    queue = deque()
    status[v_init] = VISITED_IN_QUEUE
    distance[v_init] = 0
    queue.appendleft(v_init)

    while queue:
        current = queue.popleft()
        for adj in adj_table[current]:
            if status[adj] is UNVISITED:
                status[adj] = VISITED_IN_QUEUE
                distance[adj] = distance[current] + 1
                queue.append(adj)
        status[current] = POPPED_OUT
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    vertices = list(map(lambda x: x.split(), _input[1:]))
    # assert len(vertex_info) == vertex_num

    status = [UNVISITED] * (v_num + 1)
    distance = [-1] * (v_num + 1)

    adj_table = tuple([] for _ in range(v_num + 1))
    for v_info in vertices:
        v_index, adj_num, *adj_list = map(int, v_info)
        # assert len(adj_list) == adj_num
        adj_table[v_index].extend(adj_list)

    graph_bfs(v_init=1)
    for index, v in enumerate(distance[1:], 1):
        print(index, v)

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

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

    int ans = 0;
    int A[m] = {0};
    rep(i, n) {
        int k; cin >> k;
        rep(j, k) {
            int a; cin >> a; a--;
            A[a] += 1;
        }
    }

    rep(i, m) if (A[i] == n) ans++;

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


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

using namespace std;

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define SORT(v) sort(v.begin(), v.end())
typedef long long ll;

int main()
{
    int n, m, ans;
    string s;

    cin >> n >> m;

    ans = n;

    vector<int> v(m);

    REP(i, m)
    {
        cin >> v.at(i);
        ans -= v.at(i);
    }
    ans = max(ans, -1);
    cout << ans;
}


Measured memory_bytes: 3668
from statistics import median

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

a = [ab[i][0] for i in range(n)]
b = [ab[i][1] for i in range(n)]
ma, mb = median(a), median(b)

if n % 2 == 0:
    print(int(2 * mb - 2 * ma + 1))
if n % 2 == 1:
    print(int(mb - ma + 1))


Measured memory_bytes: 52552
N, K = map(int, input().split())
A = list(map(int, input().split()))

def is_ok(x):
    cnt = 0
    for a in A:
        cnt += a // x
        if a % x == 0:
            cnt -= 1
    return cnt <= K

ng = 0
ok = max(A)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Measured memory_bytes: 104228
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    a, b = map(int, readline().split())

    ans = a - 1

    if a <= b:
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 61908
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) throws Exception {
		new Main().run();
	}
	
	void run() {
		Scanner sc=new Scanner(System.in);
		char x=sc.next().charAt(0);
		char y=sc.next().charAt(0);
		int compare=Integer.compare((int)x, (int)y);
		System.out.println(compare==1?">":compare==-1?"<":"=");
	}
	
	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
	
}


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

int main()
{
	int A, B;
	int ans = 0;
	int n = 0;

	cin >> A >> B;

	n = 1;
	
	while (n < B) {
		n--;
		n += A;
		ans++;
	}

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

Measured memory_bytes: 256
N, M = map(int, input().split())

As = []
k = 1
while k * k <= M:
    if M % k == 0:
        As.append(k)
        As.append(M // k)
    k += 1

As = sorted(As, reverse=True)

for ans in As:
    if M // ans >= N:
        print(ans)
        break

Measured memory_bytes: 3060
N = int(input())
h = list(map(int, input().split()))

jud = "Yes"
cnt = 0
for i in range(N-1):
    if h[i] > h[i+1]:
        cnt += 1
    if h[i] < h[i+1]:
        cnt = 0
    if cnt == 2:
        jud = "No"
        break
    if h[i] - h[i+1] > 1:
        jud = "No"
        break

if h[N-2] - h[N-1] > 1:
    jud = "No"

print(jud)

Measured memory_bytes: 14396
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath> 
using namespace std;
#define PI 3.141592653589793238

int main(void){

    int A, B, H, M;
    cin >> A >> B >> H >> M;

    int minute = 60 * H + M;

    double angleA = minute / 2.0;
    double angleB = minute * 6.0;   
    double angle = fmod(abs(angleA - angleB), 360);

    if(angle >= 180){
        angle = 360 - angle;
    }

    double rad = angle * PI / 180.0;

    double C;
    C = A * A + B * B - 2.0 * A * B * cos(rad);

    cout << setprecision(20) << sqrt(C) << endl;

    return 0;
}

Measured memory_bytes: 4160
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const int MOD = 1e9+7;
const ll LINF = 1e18;
const int INF = 1e9;
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;

int main()
{
    cin >> A >> B >> N;

    C = min(N,B-1);
    cout << (A*C) / B;
    
    return 0;
}

Measured memory_bytes: 3592
#include<stdio.h>
#include<string.h>

#define MAX 500000

typedef struct{
  int key,le,ri;
}Node;
 
Node tree[MAX+1];
int size;
 
void insert(int);
void inorder(int);
void preorder(int);

int main(int argc, char *argv[]){
  int n, i, first;
  first = 1;

  scanf("%d", &n);

  for(i=0;i<=n;i++) 
 tree[i].key = tree[i].le = tree[i].ri = -1;

  size = 0;

  while(n--){
    char str[100];
    scanf("%s", str);
    if(!strcmp(str, "insert")){
      int in;
      scanf("%d", &in);
      if(first){
        tree[size++].key = in;
        first = 0;
      }
      else insert(in);
    }else{
      inorder(0);
      printf("\n");
      preorder(0);
      printf("\n");
    }
  }
  return 0;
}

void insert(int x){
  int p = 0;
  while(1){
    if(x < tree[p].key){
      if(tree[p].le == -1){
        tree[p].le = size;
        tree[size++].key = x;
        break;
      }else p = tree[p].le;
    }else{
      if(tree[p].ri == -1){
        tree[p].ri = size;
        tree[size++].key = x;
        break;
      }else p = tree[p].ri;
    }
  }
}
 
void inorder(int p){
  if(tree[p].le != -1) inorder(tree[p].le);
  printf(" %d", tree[p].key);
  if(tree[p].ri != -1) inorder(tree[p].ri);
}
 
void preorder(int p){
  printf(" %d", tree[p].key);
  if(tree[p].le != -1) preorder(tree[p].le);
  if(tree[p].ri != -1) preorder(tree[p].ri);
}
 

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

using namespace std;

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

	vector<int> item_wt(n), item_val(n);

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

	// table name is dp
	vector<vector<long long int> > dp(n, vector<long long int> (bag_wt+1, 0));

	// base case: first row
	for(int wt = 0; wt<=bag_wt; wt++){
		if(wt < item_wt[0]) dp[0][wt] = 0;
		else dp[0][wt] = item_val[0];
	}

	// remaining rows
	for(int i=1; i<n; i++){
		for(int wt = 0; wt<=bag_wt; wt++){
			if(wt < item_wt[i]) dp[i][wt] = dp[i-1][wt];
			else dp[i][wt] = max(dp[i-1][wt], item_val[i] + dp[i-1][wt - item_wt[i]]);
		}
	}
	printf("%lld\n", dp[n-1][bag_wt]);
}

Measured memory_bytes: 79360
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int k,n;
    cin>>k>>n;
    vector<int>A(n);
    for (int i = 0;i<n;i++)cin>>A[i];
    vector<int>differences(n);
    differences[0] = min(abs(A[n-1]-A[0]),k-abs(A[n-1]-A[0]));
    int ans = differences[0];
    for (int i = 1;i<n;i++){
        differences[i] = A[i]-A[i-1];
        ans+=differences[i];
    }
    sort(differences.begin(),differences.end());
    ans-=differences[n-1];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
int main() {
	lint n, m, in, s = 0, ans = 0; cin >> n >> m;
	unordered_map<lint, lint> h;
	++h[0];
	for (int i = 0; i < n; ++i) {
		cin >> in;
		s = (s + in) % m;
		++h[s];
	}
	for (auto i : h) {
		ans += i.second*(i.second - 1) / 2;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3596
def main(n,a_):
  from collections import defaultdict
  lr=[[i+ai,i-ai] for i,ai in enumerate(a_)]
  rs=defaultdict(lambda:0)
  ls=defaultdict(lambda:0)
  ans=0
  for l,r in lr:
    rs[r]+=1
    ls[l]+=1
  for k in rs.keys():
    ans+=rs[k]*ls[k]
  print(ans)
if __name__=='__main__':
  n=int(input())
  a_=list(map(int,input().split()))
  #n=200000
  #a_=[3 for _ in range(n)]
  main(n,a_)


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

#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;
using ll = long long;
int mod = 1000000007;

void solve();

int main(void){
    int K; cin >> K;
    ll A[K]; rep(i, K) cin >> A[i];
    ll ulim = 2, dlim = 2; //この時点でA[K-1]=2を仮定しているのでそうじゃないものを弾く必要がある
    for(int i = K-1; i >= 1; i--){
        ulim = (ulim - (ulim % A[i])) + A[i] - 1;
        ulim -= (ulim % A[i-1]);
        if(dlim % A[i-1] > 0){
            dlim += (A[i-1] - dlim % A[i-1]);
        }
        if(ulim == 0){
            cout << -1 << endl;
            return 0;
        }
    }
    //存在するならばulim+A[0]-1, dlimは正しい答え
    ll s0 = ulim+A[0]-1;
    ll s1 = dlim;
    //cout << s0 << " " << s1 << endl;
    rep(i, K){
        if(s0 % A[i] > 0) s0 -= s0 % A[i];
        if(s1 % A[i] > 0) s1 -= s1 % A[i];
    }
    if(s0 == 2 && s1 == 2) cout << dlim << " " << ulim+A[0]-1 << endl;
    else cout << -1 << endl;
    return 0;
}

void solve(){}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
	for(int n;cin>>n,n;){
		while(n--){
			int m,e,j; cin>>m>>e>>j;
			if(m==100 || e==100 || j==100 || m+e>=180 || m+e+j>=240)
				cout<<'A'<<endl;
			else if(m+e+j>=210 || m+e+j>=150 && (m>=80 || e>=80))
				cout<<'B'<<endl;
			else
				cout<<'C'<<endl;
		}
	}
	
	return 0;
}

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

// floor(a/b) = (a-a%b)/b

int main()
{
    long long a, b, n;
    cin >> a >> b >> n;
    long long x = n;
    if (b - 1 <= n)
        x = b - 1;
    long long ans = a * x / b - a * (x / b);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3552
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<climits> //INT_MIN/MAX
using namespace std;

#define FOR(i,s,e) for(ll (i)=(s);(i)<(e);(i)++)
#define debug(x) cout<<#x<<": "<<x<<endl
typedef long long ll;

/* 2017/01/20 問題 ----- ABC047 D /Link http://abc047.contest.atcoder.jp/tasks/arc063_b */
/* -----解説等-----
問題: N 個の町が一直線上に並んでいます。行商人の高橋君は町 1 から出発し、リンゴの売買をしながら町 N へと向かいます。

はじめ高橋君は町 1 におり、リンゴを 1 つも持っていません。高橋君は次のいずれかの行動を繰り返し行います。

移動: 町 i (i<N) にいるとき、町 i+1 へ移動する。
リンゴの売買: リンゴを好きな個数だけ売買する。
ここで、町 i (1≦i≦N) ではリンゴの買値も売値もともに Ai 円とする。ここで Ai は相異なる整数です。
1 つの町で売買するリンゴの個数に制限はありませんが、旅の中で売買するリンゴの個数は合計で (買う個数と売る個数を合わせて) T 個以下にしなくてはなりません。

高橋君は旅の利益、すなわちリンゴを売った代金から買った代金を引いた値を最大にするように旅をするとします。
旅が終わったときに持っていたリンゴの価値は考えず、旅の中で売買した金額だけを考えます。

この旅に先立って、青木君は任意の町 i に対して Ai を好きな非負整数 Ai' に変えるという操作を好きなだけ行うことができます。
ただし、この操作は行うごとに |Ai−Ai'| のコストがかかります。
操作後には異なる町の間でリンゴの値段が同じになっていても構いません。

青木君の目的はできるだけ少ない合計コストの操作で高橋君の利益を少なくとも 1 円下げることです。
合計コストの最小値を求めてください。

ただし、元の状態で高橋君が 1 円以上の利益を上げられることは仮定して構いません。

制約
1≦N≦105
1≦Ai≦109 (1≦i≦N)
Ai は相異なる
2≦T≦109
入力の状態では高橋君は 1 円以上の利益を上げられることが保証される




*/
#define INF INT_MAX/2
int N, T, a[100000];
int minn = INF, maxn = -INF;
int nowmax = -1;
int cnt = 0;
int ans = 0;

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

    cin >> N >> T;
    FOR(i, 0, N) {
        cin >> a[i];
    }

    minn = a[0];
    FOR(i, 0, N) {
        
        if (minn > a[i]) {
            maxn = -INF;
            minn = a[i];
        }

        if (nowmax == a[i]- minn)cnt++;
        else if (nowmax < a[i] - minn) {
            nowmax = a[i] - minn;
            cnt = 1;
        }


    }


    ans = cnt;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(){
  int n, u, k, v, i, j, A[101][101];
  
  scanf("%d", &n);

  for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) A[i][j] = 0;

  for(i = 1; i <= n; i++){
    scanf("%d%d", &u, &k);
    for(j = 1; j <= k; j++){
      scanf("%d", &v);
      A[u][v] = 1;
    }
  }

  for(i = 1; i <= n; i++){
    for(j = 1; j < n; j++){
      printf("%d ", A[i][j]);
    }
    printf("%d\n", A[i][j]);
  }
  
  return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define rep(i, b) for(int i = 0; i < b; i++)
#define repr(i, b) for(int i = b - 1 ;i >= 0; i--)
#define It(m) for(auto it = m.begin(); it != m.end(); it++)
#define N 500500
#define PI 3.14159265358979323846264338327950L
#define speed ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

signed main(){
    int n; cin >> n;
    vi v(n);
    rep(i, n) { 
        cin >> v[i];
    }
    int mn = INT_MAX;
    int money = 1000;
    int cnt = 0;

    rep(i, n) {
        if(mn >= v[i]) {
            mn = v[i];
        } else {
            cnt = money / mn;
            money = (money % mn) + (cnt * v[i]);
            mn = v[i];
        }
    }
    cout << money << endl;
    return 0;
}

Measured memory_bytes: 3628
n,k=map(int,input().split())
ki=[]
ai=[]
for i in range(1,k+1):
  ki.append(int(input()))
  ai.append(list(map(int,input().split())))

s=list(range(1,n+1))

for i in range(1,k+1):
  for j in range(len(ai[i-1])):
    if ai[i-1][j-1] in s:
      s.remove(ai[i-1][j-1])
    
print(len(s))

Measured memory_bytes: 9148
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main(void)
{
    int a,ans=1;
    cin >> a;
    vector<int> b(a);
    for(int i =0;i < a;i++)
        cin >> b[i];

    sort(b.begin(),b.end());

    for(int i = 1;i < a;i++){
        if(b[i] > b[i-1])
            ans++;
    }
    cout << ans << endl;

}


Measured memory_bytes: 256