akhauriyash/Code-Regression huggingface dataset:
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define FILE ifstream in("input.txt");ofstream out("output.txt");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

ll a,mod;
vec<vec<ll>> l, pr, sf;
vec<ll> dp, ans;

void efs(int v, int p){
    int n = -1, i=0;
    for(int h : l[v]){
        if(h==p) n = i;
        else efs(h, v);
        i++;
    }
    if(n!=-1) l[v].erase(l[v].begin()+n);
}

void dfs(int v){
    dp[v] = 1;
    vec<ll> m;
    for(ll h : l[v]){
        dfs(h);
        m.pb(dp[h]+1);
        dp[v] *= dp[h]+1;
        dp[v]%=mod;
    }
    int sz = m.size();
    pr[v] = vec<ll>(sz);
    sf[v] = vec<ll>(sz);
    for(int q=0; q<sz; q++){
        pr[v][q] = m[q]*(q ? pr[v][q-1] : 1);
        pr[v][q] %= mod;
    }
    for(int q=sz-1; q>=0; q--){
        sf[v][q] = m[q]*(q<sz-1 ? sf[v][q+1] : 1);
        sf[v][q] %= mod;
    }
}

void jfs(int v, ll res){
    ans[v] = (dp[v]*(res+1))%mod;
    for(int q=0; q<l[v].size(); q++){
        int h = l[v][q];
        ll iso = (q ? pr[v][q-1] : 1) * (q+1<l[v].size() ? sf[v][q+1] : 1);
        iso %= mod;
        jfs(h, ((res+1)*iso)%mod);
    }
}

int main() {
    fast;
    cin>>a>>mod;
    dp = vec<ll>(a, 0);
    ans = vec<ll>(a, 0);
    l = vec<vec<ll>>(a, vec<ll>());
    pr = vec<vec<ll>>(a, vec<ll>());
    sf = vec<vec<ll>>(a, vec<ll>());
    for(int q=0; q<a-1; q++){
        ll x,y; cin>>x>>y; x--, y--;
        l[x].pb(y);
        l[y].pb(x);
    }
    efs(0, -1);
    dfs(0);
    ans[0] = dp[0];
    //for(int q=0; q<a; q++)cout<<q+1<<": ";for(ll i : pr[q]) cout<<i<<" "; cout<<endl;
    for(int q=0; q<l[0].size(); q++){
        ll res = (q ? pr[0][q-1] : 1) * (q+1<l[0].size() ? sf[0][q+1] : 1);
        res %= mod;
        jfs(l[0][q], res);
    }
    for(ll i : ans) cout<<i<<"\n";
}

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

 using namespace std;

 int main() {
   int mina, maxz, i;
   string S;
   cin >> S;

   mina = S.length();
   maxz = 0;
   for (i = 0; i < S.length(); i++) {
     if (S.at(i) == 'A') mina = min(mina, i);
   }
   for (i = mina; i < S.length(); i++) {
     if (S.at(i) == 'Z') maxz = max(maxz, i);
   }
   cout << maxz - mina + 1 << endl;
 }


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#define ll long long

using namespace std;


int main() {
	int cs = 1;
	int ipt;
	while (cin >> ipt) {
		if (ipt == 0)return 0;
		cout << "Case " << cs << ": " << ipt << endl;
		cs++;
	}

}




Measured memory_bytes: 3096
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

const int DMAX = 160*80+5;
bool dp[85][85][DMAX];
int main() {
  int h,w;
  cin >> h >> w;
  vector<vector<int>> a(h,vector<int>(w));
  vector<vector<int>> b(h,vector<int>(w));
  rep(i,h)rep(j,w) cin >> a[i][j];
  rep(i,h)rep(j,w) cin >> b[i][j];


  dp[1][0][0] = dp[0][1][0] = true;
  rep(i,h)rep(j,w){
    int nd = abs(a[i][j] - b[i][j]);
    rep(d,DMAX){
      if(dp[i][j+1][d]){
        dp[i+1][j+1][d+nd] = true;
        dp[i+1][j+1][abs(d-nd)] = true;
      }
      if(dp[i+1][j][d]){
        dp[i+1][j+1][d+nd] = true;
        dp[i+1][j+1][abs(d-nd)] = true;
      }
    }
  }
  
  rep(i,DMAX){
    if(dp[h][w][i]){
      cout << i << endl; 
      break;
    }
  }

}


Measured memory_bytes: 86912
# -*- coding: utf-8 -*-
 
S = input()
T = input()

ans = len(T)
for i in range( len(S)-len(T)+1 ):
  count = len(T)
  for j in range( len(T) ):
    
    if( S[i+j]==T[j] ):
      count -= 1
  
  if( count < ans ):
    ans = count

print(ans)

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

int main() {
  int n, x, y;
  cin >> n >> x >> y;
  x--; y--;
  for(int k=1; k<n; k++){int ans = 0;rep(i, n) {
    int j;
    if (i <= x-k) ans++;
    else if (i <= x) {
      j = i+k;
      if (j <= y) {
        if (j < y-k+1+x-i) ans += 2;
        else if (j == y-k+1+x-i) ans++;
      }
      j = y+k-1-x+i;
      if ((j > y) && (j < n)) ans++;
    } else if (i < min(x+k,y)) {
      j = i+k;
      if (j <= y) {
        if (j < y-k+1+i-x) ans += 2;
        else if (j == y-k+1+i-x) ans++;
      }
      int j2 = y+k-1-i+x;
      if ((max(j2, j) > y) && (max(j2, j) < n)) ans++;
    }
    else if (i < n-k) ans++;
  } cout << ans << endl;}
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define PI 3.1415926535
const long long int MOD = 1e9+7;
#define pb push_back
#define mp make_pair
#define fill(a)  memset(a, 0, sizeof (a))
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define watch(x) cout << (#x) << " is " << (x) << endl;
const long long int MAXX = 2e5+5;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector< iii > viii;

ll lcm(ll a, ll b) {
   return a / __gcd(a, b) * b;
}
int XOR(int x, int y){
  return (x | y) & (~x | ~y);
}
bool cmp(const pair<int,int> &a,const pair<int,int> &b) {
    return (a.second < b.second);
}
// bool isl = binary_search(x.begin(), x.end(), 5);
// __builtin_popcount(x)  - Returns the number of set bits in x
const long long int N = 1e6;
int binsearch(int lo, int hi){
    while(lo<hi){
        int mid=(lo+hi)/2;
        if((mid))   // check(mid)
            hi=mid;
        else
            lo=mid+1;
    }
    return lo;
}
int power(int x,int y){
    int res=1;
    while(y>0){
      if(y&1) res=((res*x));

      y/=2;
      x=((x*x));
    }
    return res;
}

int main(){
    FAST
    int x;
    cin>>x;
    if(x>=30) cout<<"Yes";
    else cout<<"No";
    return 0;
}


Measured memory_bytes: 3608
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int N  = 9;
		
		String[] names = new String[N];
		int[] num = new int[N];
		int[] prices = new int[N];
		
		for(int i = 0; i < N; i++){
			names[i] = sc.next();
			int pre = sc.nextInt();
			int post = sc.nextInt();
			
			num[i] = pre + post;
			prices[i] = pre * 200 + post * 300;
		}
		
		for(int i = 0; i < N; i++){
			System.out.println(names[i] + " " + num[i] + " " + prices[i]);
		}

	}

}

Measured memory_bytes: 12000
#include <iostream>
#include <string>
using namespace std;
int main()
{
	string s;
	cin >> s;
  	int a = std::stoi(s.substr(0, 2));
  	int b = std::stoi(s.substr(2, 2));
  	if (1 <= a && a <= 12) {
	  	if (1 <= b && b <= 12) {
          s = "AMBIGUOUS";
        }
        else {
          s = "MMYY";
        }
    }
    else {
	  	if (1 <= b && b <= 12) {
          s = "YYMM";
        }
        else {
          s = "NA";
        }
    }
  	cout << s << endl;
	return(0);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define ALL(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

int prime[100001] = {};

bool IsPrime(int num)
{
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}
int main()
{
    int q;
    cin >> q;
    vector<pair<int, int>> p(q);
    rep(i, q)
    {
        int l, r;
        cin >> l >> r;
        p[i] = make_pair(l, r);
    }
    for (int i = 1; i <= 100000; i++)
    {
        if (IsPrime(i) && IsPrime((i + 1) / 2))
        {
            prime[i] = prime[i - 1] + 1;
        }
        else
        {
            prime[i] = prime[i - 1];
        }
    }
    rep(i, q)
    {
        cout << prime[p[i].second] - prime[p[i].first - 1] << endl;
    }

    return 0;
}


Measured memory_bytes: 1792
N = int(input())
A = list(map(int, input().split()))
B = [False] * N
for i in range(N, 0, -1):
    B[i-1] = (A[i-1] + sum(B[j-1] for j in range(i * 2, N+1, i))) & 1
C = [i for i, a in enumerate(B, 1) if a]
print(len(C))
print(*C)

Measured memory_bytes: 14136
#include<stdio.h>
#include<string.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i,N) for(int i=0;i<(int)N;i++)
const int pw[13]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441};
static inline void OUT(int x){if(x<0)putchar('-'),x=-x;if(x>=10)OUT(x/10);putchar(x%10+48);}
int main(void)
{
  int N,len=0,carry[200000],temp[531441],A[531441],add[531441];char T[200001];
  if(scanf("%d %s",&N,T)!=0)len=strlen(T);
  rep(i,N)
  {
    int flip=0;
    memset(add,0,pw[i]*sizeof(int));
    rep(j,len)
    {
      if(T[j]=='S'){flip^=1;}
      else
      {
        int x=carry[j];
        add[x]=(add[x]+(flip?2:1))%3;
        carry[j]+=(3-add[x])%3*pw[i];
      }
    }
    memcpy(temp,A,pw[i]*sizeof(int));
    rep(c,3){rep(j,pw[i])A[c*pw[i]+j]=temp[j]+(flip?2:1)*(c+add[j])%3*pw[i];}
  }
  rep(i,pw[N])OUT(A[i]),putchar(' ');
}

Measured memory_bytes: 8384
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
	for (T& x : vec) is >> x;
	return is;
}

int main() {

	int N;
	cin >> N;

	vector<int> a(N);
	cin >> a;

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

	int x = 0, y = 0;
	for (int i = N - 1; i >= 0;)
	{
		x += a[i];
		i--;
		if (i < 0) break;
		y += a[i];
		i--;
	}

	cout << x - y << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long 
#define pb push_back
#define fr first
#define sc second
#define sz(v) ((int)(v).size())
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,p) for(int i=a-1;i>=p;i--) 
#define M 1000000007
#define vi vector<int>
#define vp vector<pair<int,int> >
#define ml map<int,int>
#define MPI 3.1415926536
using namespace std;
int temp=0,r,l,w,k=0,m1,e,p,q,ans,k1=0,k2=0,d=0,a=0,b=0,s=0,x,y,min1=1000000010,max1=0,m,c=0,t=0,i,n,c1=0,tot=0,t1,k4=0,c2=0,j=0,k3=0;char ch,ch1,ch2;string s1,s2,s3;
signed main()
{
cin>>n;
int a1[n][3];
int dp[n][3];
rep(i,0,n)
{
	rep(j,0,3)cin>>a1[i][j];
}
dp[0][0]=a1[0][0];
dp[0][1]=a1[0][1];
dp[0][2]=a1[0][2];
rep(i,1,n)
{
	dp[i][0]=a1[i][0]+max(dp[i-1][1],dp[i-1][2]);
	dp[i][1]=a1[i][1]+max(dp[i-1][0],dp[i-1][2]);
	dp[i][2]=a1[i][2]+max(dp[i-1][0],dp[i-1][1]);
}
cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
}

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

using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a<6){
        cout<<"0";
    }
    else if(a<13){
        cout<<b/2;
    }
    else{
        cout<<b;
    }

    return 0;
}

Measured memory_bytes: 3476
#include <iostream>
#include <string>

int main(){
    int m;
    int ap=0;
    int bp=0;
    std::string a,b;
    std::cin >> m;
    for(int n=0;n<m;n++){
        std::cin >> a >> b;
        if(a>b)ap+=3;
        if(a<b)bp+=3;
        if(a==b){ap+=1;bp+=1;}
    }
    std::cout << ap << " " << bp << std::endl;
    return 0;
}

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

#define rep3(i, s, n ,a) for (int i = (s); i < (int)(n); i+=a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> light;
    rep(i, m){
        int k, s;
        vector<int> tmp_light(n, 0);
        cin >> k;
        rep(j, k){
            cin >> s;
            tmp_light[s-1] = 1;
        }
        int code=0, two=1;
        rep(j, n){
            code += two * tmp_light[n-j-1];
            two <<= 1;
        }
        light.push_back(code);
    }
    vector<bool> p;
    rep(i, m){
        bool p_num;
        cin >> p_num;
        p.push_back(p_num);
    }
    int cnt=0;

    rep(bit, (1<<n)){
        int i;
        for(i=0; i<m; i++){
            int res = light[i] & bit;
            int on=0;
            rep(j, n){
                on += res%2;
                res /= 2;
            }
            if(on%2!=p[i]){
                break;
            }
        }
        if(i==m){
            cnt++;
        }
    }

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



Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

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

		int n = scanner.nextInt();
		int m = scanner.nextInt();

		int[][] num = new int[n + 1][n + 1];
		for (int[] t : num) {
			Arrays.fill(t, -1);
		}
		for (int i = 0; i < m; i++) {
			StringTokenizer tokenizer = new StringTokenizer(scanner.next(), ",");
			int a = Integer.valueOf(tokenizer.nextToken());
			int b = Integer.valueOf(tokenizer.nextToken());
			int c = Integer.valueOf(tokenizer.nextToken());
			int d = Integer.valueOf(tokenizer.nextToken());
			num[a][b] = c;
			num[b][a] = d;

		}
		StringTokenizer tokenizer = new StringTokenizer(scanner.next(), ",");
		int q = Integer.parseInt(tokenizer.nextToken());
		int r = Integer.parseInt(tokenizer.nextToken());
		int ans = Integer.parseInt(tokenizer.nextToken())
				- Integer.parseInt(tokenizer.nextToken());
		int qs = getYen(q, r, num);
		int rs = getYen(r, q, num);
		ans = ans - qs - rs;
		System.out.println(ans);
	}

	public static int getYen(int q, int r, int[][] num) {
		int[] cost = new int[num.length];
		Arrays.fill(cost, Integer.MAX_VALUE);
		cost[q] = 0;
		getYen(q, num, cost);
		return cost[r];
	}

	public static void getYen(int q, int[][] num, int[] cost) {
		for (int j = 1; j < num.length; j++) {
			if (num[q][j] != -1 && num[q][j] + cost[q] < cost[j]) {
				cost[j] = num[q][j] + cost[q];
				getYen(j, num, cost);
			}
		}
	}
}

Measured memory_bytes: 17184
#include <bits/stdc++.h>
using namespace std;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
 
typedef long long ll;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl

struct nodo
{
	int v, anti, antj;
	char a;
};

nodo SET(int v, int i, int j, char a)
{
	nodo aux;
	aux.v = v; aux.anti=i; aux.antj=j; aux.a=a;
	return aux;
}
 
string LCS(string s1, string s2)
{
	vector < vector <nodo> > dp(3005,vector <nodo>(3005));
	int n=s1.size(), m=s2.size();
	
	
	forn(i,n+1)
	{
		forn(j,m+1)
		{
			if(i==0 || j==0) continue;
			if(s1[i-1]==s2[j-1])
			{
				dp[i][j]=SET(dp[i-1][j-1].v+1,i-1,j-1,s1[i-1]);
				continue;
			}
			if(dp[i-1][j].v > dp[i][j-1].v)
			{
				dp[i][j]=SET(dp[i-1][j].v,i-1,j,'a');
			}
			else dp[i][j]=SET(dp[i][j-1].v,i,j-1,'a');
		}
	}
	
	string ans; 
	while(n!=0 && m!=0)
	{
		if(dp[n][m].anti == n-1 && dp[n][m].antj == m-1) ans.pb(dp[n][m].a);
		int aux = n;
		n=dp[n][m].anti; m=dp[aux][m].antj;
	}
	reverse(all(ans));
	return ans;
}
 
int main()
{ 
	FIN;
	
	#ifdef input
		freopen("test3.txt", "r", stdin);
	#endif
	
	string s1, s2;
	cin >> s1 >> s2;
	cout << LCS(s1,s2) << endl;
	return 0;
}


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

#define vec                vector<int>
#define vecll              vector<ll>
#define vecst              vector<string>
#define vecb               vector<bool>
#define vec2(var, n, m)    vector<vector<int>> var(n, vector<int>(m, 0))
#define vecll2(var, n, m)  vector<vector<ll>> var(n, vector<ll>(m, 0))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define f_sum(var)       accumulate(all(var), 0)
#define f_sumll(var)     accumulate(all(var), 0LL)
#define chmin(v1, v2)    v1 = min(v1, v2)
#define chmax(v1, v2)    v1 = max(v1, v2)
#define mp(v1, v2)       make_pair(v1, v2)
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << var << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << var;
#define prt2(v1, v2)     cout << v1 << " " << v2 << "\n"
#define prt3(v1, v2, v3) cout << v1 << " " << v2 << " " << v3 << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
void prtok(bool ok){prt(ok ? "Yes" : "No");}
//----------------------------------------------------------------

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

  if(s.size()>k){
    rep(i,k){
      cout << s[i];
    }
    prt("...");
  } else {
    prt(s);
  }

}


Measured memory_bytes: 3600
s = input()

left = int(s[:2])
right = int(s[2:])

ans = "NA"

if 0 < left <13:
    if 0 < right < 13:
        ans = "AMBIGUOUS"
    else:
        ans = "MMYY"
else :
    if 0 < right < 13:
        ans = "YYMM"



print(ans)

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main()
{
	int n;
	string S;
	cin >> n;
	cin >> S;
	if (n%2 == 1){
		cout << "No" << endl;
		return 0;
	}
	int flag = 0;
	int haf = n /2;
	for (int i = 0; i<haf; i++)
	{
		if(S[i] != S[haf+i])
		{
			flag = 1;	
		}
	}
	
	if(flag == 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 3576
#include <iostream>

int main() {
  std::string last_week_contest;

  std::cin >> last_week_contest;

  std::string current_week_contest;
  if(last_week_contest == "ABC") {
    current_week_contest = "ARC";
  } else if (last_week_contest == "ARC") {
    current_week_contest = "ABC";
  }

  std::cout << current_week_contest << std::endl;

  return 0;
}


Measured memory_bytes: 3628
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct ed{int n,t;}e[400010];
int n,m,l,k,h[200010],g[200010],op[200010],nd[200010];
double s=0;
int lb(int x)
{
	return x&(-x);
}
void at()
{
	for(int i=op[k];i<=n;i+=lb(i)) g[i]+=l;
	for(int i=nd[k];i<=n;i+=lb(i)) g[i]-=l;
}
void gt(int x)
{
	int y=0;
	for(int i=op[x];i;i-=lb(i)) y+=g[i];
	printf("%d ",y);
}
void dfs(int x,int f)
{
	op[x]=k++;
	for(int i=h[x];i;i=e[i].n)
	{
		if(e[i].t==f) continue;
		dfs(e[i].t,x);
	}
	nd[x]=k;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n-1;i++)
	{
		scanf("%d%d",&k,&l);
		e[i*2+1].t=l;
		e[i*2+1].n=h[k];
		h[k]=i*2+1;
		e[i*2+2].t=k;
		e[i*2+2].n=h[l];
		h[l]=i*2+2;
	}
	k=1;
	dfs(1,0);
	while(m--)
	{
		scanf("%d%d",&k,&l);
		at();
	}
	for(int i=1;i<=n;i++) gt(i);
	putchar('\n');
	return 0;
}

Measured memory_bytes: 17792
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
ll A[1 << 18];
ll max1[1 << 18], max2[1 << 18];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < (1 << N); i++) cin >> A[i];
	for (int i = 0; i < (1 << N); i++) max1[i] = A[i];
	for (int i = 0; i < N; i++) {
		for (int bit = 0; bit < (1 << N); bit++) {
			if (bit&(1 << i)) continue;
			int nbit = bit | (1 << i);
			if (max1[bit] >= max1[nbit]) {
				max2[nbit] = max1[nbit];
				max1[nbit] = max1[bit];
			}
			else if (max1[bit] >= max2[nbit]) {
				max2[nbit] = max1[bit];
			}
			if (max2[bit] >= max2[nbit]) {
				max2[nbit] = max2[bit];
			}
		}
	}
	ll prev = 0;
	for (int bit = 1; bit < (1 << N); bit++) {
		ll now = max(max1[bit] + max2[bit], prev);
		cout << now << endl;
		prev = now;
	}
}

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

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // rdfile("_input.txt");

    int A, B;
    cin >> A >> B;
    cout << (A <= 8 && B <= 8 ? "Yay!" : ":(") << endl;

    return 0;
}

Measured memory_bytes: 256
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

a,b = mi()

for i in range(10**4):
    if int(i * 0.08) == a and int(i*0.1) == b:
        print(i)
        exit()
print(-1)


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100
int n;
char A[3][MAXN+5];
int ans;
int main()
{
    scanf("%d",&n);
    scanf("%s%s%s",A[0]+1,A[1]+1,A[2]+1);
    for(int i=1;i<=n;i++)
    {
        if(A[0][i]==A[1][i]&&A[0][i]==A[2][i]&&A[1][i]==A[2][i])ans+=0;
        else if(A[0][i]==A[1][i]||A[0][i]==A[2][i]||A[1][i]==A[2][i])ans++;
        else ans+=2;
    }
    printf("%d",ans);
}

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

int main(){
    constexpr long long m = 1000000007;

    long long N, M;
    scanf("%lld%lld", &N, &M);

    vector<long long> A(N), B(M);
    for(auto& i : A)scanf("%lld", &i);
    for(auto& i : B)scanf("%lld", &i);

    sort(A.rbegin(), A.rend());
    sort(B.rbegin(), B.rend());

    long long x(0), y(0), n(N * M), k(0), a(0), b(0), r(1);
    for(; n > 0; --n){
        if(a < N && A[a] == n){
            if(b < M && B[b] == n){
                ++x;
                ++y;
                ++a;
                ++b;
            }else{
                r *= y;
                ++x;
                ++a;
            }
        }else{
            if(b < M && B[b] == n){
                r *= x;
                ++y;
                ++b;
            }else{
                r *= max(0LL, x * y - k);
            }
        }
        ++k;
        r %= m;
        if(a < N && b < M && (A[a] == n || B[b] == n))return 0 & puts("0");
    }

    printf("%lld\n", r);

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define MOD_BY 1000000

int memo1[101][2];

int tansaku1(int pos,int max,int up) {
	int ans;
	if(pos>max) {
		return up?0:1;
	}
	if(memo1[pos][up]>0)return memo1[pos][up]-1;
	ans=tansaku1(pos+1,max,up);
	ans+=tansaku1(pos+1,max,up?0:1);
	ans%=MOD_BY;
	memo1[pos][up]=ans+1;
	return ans;
}

int memo2[102][102][102][3];

int tansaku2(int up,int mid,int down,int pos,int max) {
	int ans=0;
	int themax;
	if(up<=max && mid<=max && down<=max) {
		if(memo2[up][mid][down][pos]>0)return memo2[up][mid][down][pos]-1;
	}
	switch(pos) {
		case 0: /* up */
			if(up>max)return 0;
			ans+=tansaku2(up+1,mid,down,0,max);
			ans+=tansaku2(up,up+1,down,1,max);
			themax=mid;
			if(down>themax)themax=down;
			ans+=tansaku2(up,up,up+1,2,max)*(up-themax);
			break;
		case 1: /* mid */
			if(mid>max)return 0;
			ans+=tansaku2(up,mid+1,down,1,max);
			ans+=tansaku2(mid+1,mid,down,0,max);
			ans+=tansaku2(up,mid,mid+1,2,max);
			break;
		case 2: /* down */
			if(down>max)return 1;
			ans+=tansaku2(up,mid,down+1,2,max);
			ans+=tansaku2(up,down+1,down,1,max);
			themax=mid;
			if(up>themax)themax=up;
			ans+=tansaku2(down+1,down,down,0,max)*(down-themax);
			break;
	}
	ans%=MOD_BY;
	memo2[up][mid][down][pos]=ans+1;
	return ans;
}

int main(void) {
	int N,M;
	scanf("%d%d",&N,&M);
	if(M==1) {
		printf("%d\n",tansaku1(0,N,1));
	} else if(M==2) {
		printf("%d\n",tansaku2(1,0,0,0,N+1));
	} else return 1;
	return 0;
}

Measured memory_bytes: 12920
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int H, W;
int c[10][10];
int A[200][200];

int main() {
  cin >> H >> W;
  REP(i, 10) REP(j, 10) cin >> c[i][j];
  REP(i, H) REP(j, W) cin >> A[i][j];
  REP(k, 10) REP(i, 10) REP(j, 10) c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
  ll ans = 0;
  REP(i, H) REP(j, W) {
    if (A[i][j] != -1) ans += 1ll * c[A[i][j]][1];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N ;
  cin >> N;
  vector<int> A(N);
  vector<bool> Add(N);
  vector<int> B(N);

  for(int i = 0; i <N; i++){
    cin >> A.at(i) ;
    if(i > 0 && A.at(i) == A.at(i-1) + 1){
      Add.at(A.at(i-1) -1) = true;
    }
    else if(i > 0){
      Add.at(A.at(i-1) -1) = false;
    }
  }
  
  int ans = 0;
  int score;
  for(int i = 0; i < N; i++){
    cin >> score;
    ans += score;
  }
  
  int plus;
  for(int i = 0; i < N -1; i++){
    cin >>plus;
    if(Add.at(i)){ ans+= plus; }
  }
  
  cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){   
        ll n,m,x;
        cin >> n >> m >> x;
        
        vector<ll> a(n);
        for(ll a_i = 0; a_i <n; a_i++){
           cin >> a[a_i];
        }
        
        vector<ll> b(m);
        for(ll b_i =0; b_i <m; b_i++){
           cin >> b[b_i];
        }
        
        ll sum=0,count=0,temp=0,i=0,j=0;        
        
        while(i<n && sum+a[i]<=x){    
            sum+=a[i];
            i++;
        }
        count=i;        
       
        while(j<m && i>=0){          
            sum+=b[j];             
            j++;
            while(sum>x && i>0){
                i--;
                sum-=a[i];
            }
            if(sum<=x && i+j>count)
                count=i+j;
        }
        cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 6352
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
//#define int ll
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, int>
#define vi vector <int>
const ll nmax=1e5+2;
const ll mod = 998244353;
int n, m;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>m;
    if(n%2!=m%2) cout<<"IMPOSSIBLE";
    else cout<<(n+m)/2;
}


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

vector<P>E[200000];
int d[200000];

void dfs(int v,int p){
	for(auto u:E[v]){
		if(u.second!=p){
			d[u.second]=(d[v]+u.first)%2;
			dfs(u.second,v);
		}
	}
}

int main(){
	int n;cin>>n;
	rep(i,n-1){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);a--;b--;
		E[a].push_back(P(c,b));
		E[b].push_back(P(c,a));
	}
	dfs(0,-1);
	rep(i,n){
		printf("%d\n",d[i]);
	}
}

Measured memory_bytes: 14744
// B - Roller Coaster
#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> h(n);
	for (int i = 0; i < n; i++) cin >> h[i];
	int ans = 0;
	for (int i = 0; i < n; i++)
		if (h[i] >= k) ans++;
	cout << ans << endl;

	return 0;
}


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

int main(void) {
  int n;
  cin >> n;
  vector<int> w(n);
  for (int i = 0; i < n; i++) {
    cin >> w.at(i);
  }
  int ans = 1e9;
  for (int i = 1; i < n; i++) {
    int l = 0, r = 0;
    for (int j = 0; j < i; j++) {
      //sum from 0.to i.S1
      l += w.at(j);
    }
    for (int j = i; j < n; j++) {
      // sum form i to n.S2
      r += w.at(j);
    }
    ans =min(ans, abs(l-r));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
string s;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    for (int i = 0; i < s.size() - 1; i++)
        if (s[i] == s[i + 1])
        {
            cout << "Bad"
                 << "\n";
            return 0;
        }
    cout << "Good"
         << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long h[5],num;
int main()
{
	int n;
	cin>>n;
	string s[n];
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
		if(s[i][0]=='M') h[0]++;
		if(s[i][0]=='A') h[1]++;
		if(s[i][0]=='R') h[2]++;
		if(s[i][0]=='C') h[3]++;
		if(s[i][0]=='H') h[4]++;
    }
	
	for(int i=0;i<3;i++)
		for(int j=i+1;j<4;j++)
			for(int k=j+1;k<5;k++)
				num+=h[i]*h[j]*h[k];
	cout<<num<<endl;
	return 0;
}

Measured memory_bytes: 6144
N = int(input())

dic = [3, 5, 7]

ans = set()
def dfs(s):
    if s:
        if int(s) <= N:
            if len(set(s)) == 3:
                ans.add(s)
        else:
            return
    for c in '753':
        dfs(s+c)

dfs("")
print(len(ans))


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

int bubbleSort(int A[], int N){
  int sw = 0;
  bool flag = 1;
  for(int i=0;flag;i++){
    flag = 0;
    for(int j=N-1;j>=i+1;j--){
      if(A[j]<A[j-1]){
        swap(A[j],A[j-1]);
        flag = 1;
        sw++;
      }
    }
  }
  return sw;
}

int main(){
  int A[100],N,sw;
  cin >> N;
  for(int i=0;i<N;i++)cin>> A[i];

  sw = bubbleSort(A,N);

  for(int i=0;i<N;i++){
    if(i)cout << " ";
    cout << A[i];
  }
  cout << endl;
  cout << sw << endl;

  return 0;
}



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

int main() {

    int a[5];
    int min = 9;
    int minIdx = 0;
    for (int i=0; i<5; i++) {
        cin >> a[i];
        if (a[i] % 10 != 0 && a[i] % 10 < min) {
            min = a[i] % 10;
            minIdx = i;
        }
    }

    int ans = 0;
    for (int i=0; i<5; i++) {
        if (i == minIdx) {
            ans += a[i];
        }
        else {
            ans += (a[i] + 9) / 10 * 10;
        }
    }

    cout << ans << endl;

    return 0;
}


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

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

    for(int x = o/10000; x >= 0; x--){
        for(int y = (o-x*10000)/5000; y >= 0; y--){
            int z = (o-x*10000-y*5000)/1000;
            if(x+y+z == n){
                cout << x << " " << y << " " << z << endl;
                return 0;
            }
        }
    }

    cout << "-1 -1 -1" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

ll A, B, N;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> N >> A >> B;
    ll rem = N%(A+B);
    ll m = N/(A+B);
    cout << m*A+min(rem, A) << endl;
}

Measured memory_bytes: 384
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

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

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const ld EPS = 1e-6;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const char nl = '\n';

template <typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <typename T> inline T lcm(T a, T b) { return a / gcd(a, b) * b; }
template <class T> void ckmin(T& a, T b) { a = min(a, b); }
template <class T> void ckmax(T& a, T b) { a = max(a, b); }

// (Integer/Long).bitCount(x)
int pct(int x) { return __builtin_popcount(x); }
int pct(ll x) { return __builtin_popcountll(x); }

void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << h; if (sizeof...(t)) cerr << ", "; DBG(t...); }

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); }
}

// Binary Exponentiation
ll pow(ll b, ll e, ll m = 0LL, ll ans = 1LL) { while (e) { if (e & 1LL) { ans *= b; if (m) ans %= m; } b *= b, e >>= 1LL; if (m) b %= m; } return ans; }



void solve(int tcn) {
	int n;
	cin >> n;
	vector<ll> a(n);
	F0R(i, n) cin >> a[i];
	ll mon = 1000LL;
	F0R(i, n-1) {
		if (a[i] < a[i+1]) {
			ll tak = mon / a[i];
			mon += tak * (a[i+1] - a[i]);
		}
	}
	cout << mon << nl;
}

int main() {
    setIO();

    int t = 1; //cin >> t;
	for (int i = 1; i <= t; ++i) {
		//cout << "Case #" << i << ": ";
		solve(i);
	}
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_temp>
using smaller_queue = priority_queue<Q_temp, vector<Q_temp>, greater<Q_temp>>;

const ll MOD = (ll)(1e9 + 7);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b)
{
  return (a + b - 1) / b;
}

inline void finish()
{
  cout << -1 << endl;
  exit(0);
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(50) << setiosflags(ios::fixed);

  ll n;
  cin >> n;
  ll a[100010];
  rep(i, n) cin >> a[i];
  ll l = 2, r = 3;
  for (ll i = n - 1; i >= 0; --i)
  {
    l = CEIL(l, a[i]) * a[i];
    r = CEIL(r, a[i]) * a[i];
  }
  if (l == r)
    finish();
  cout << l << " " << r - 1 << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>

int main(){
    int num;
    int flag = 0;
    std::cin >> num;

    std::string *a = new std::string[num];
    std::string temp;
    int *b = new int[num];

    int sum = 0;
    int i;

    for(i=0; i<num; i++){
        std::cin >> a[i] >> b[i];
    }
    std::cin >> temp;

    for(i=0; i<num; i++){
        if((flag == 1)||(temp == a[i])) {
            if(flag == 0) {
                flag = 1;
                continue;
            }
            sum += b[i];
        }
        
        //std::cout << a[i] << ", " << b[i] << std::endl;
    }
    std::cout << std::endl;
    std::cout << sum << std::endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strAry = br.readLine().split(" ");
        
        int W = Integer.parseInt(strAry[0]);
        int H = Integer.parseInt(strAry[1]);
        int x = Integer.parseInt(strAry[2]);
        int y = Integer.parseInt(strAry[3]);
        int r = Integer.parseInt(strAry[4]);
        
         if ( (x - r >= 0 && x + r <= W) && (y - r >= 0 && y + r <= H) ) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 24396
const lines=readlines(open("/dev/fd/0"))
input()=shift!(lines)
int(s::String)=parse(Int32,s)
intSub(s::SubString{String})=parse(Int32,s)
intLine()=map(intSub,split(input()))
function main()
    d=Dict('A'=>'T','T'=>'A','G'=>'C','C'=>'G')
    println(d[input()[1]])
end
main()

Measured memory_bytes: 112564
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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 int INF=1001001001;
const int mod=1e9+7;

int main(){
  int64_t x;
  cin>>x;
  cout<<1000*(x/500)+(x%500)/5*5<<endl;
  return 0;
}

Measured memory_bytes: 3640
/*	
*  Sachin Mittal
*/
#include<bits/stdc++.h>
#define int long long
#define M 998244353
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define rep(i,j,n) for(int i=j;i<n;i++)
#define F first
#define S second
#define lb lower_bound
#define mem0(dp) memset(dp,0,sizeof(dp))
#define mem1(dp) memset(dp,-1,sizeof(dp))
#define pb push_back
#define sz(s) (int)(s.size())
#define debug(x) cout << #x << " = " << x << '\n';
using namespace std;

void solve()
{
   	int a, b, n;
   	cin >> a >> b >> n;
   	int x = min(n, b-1);
   	//cout << x << " ";
   	cout << (a * x) / b - a * (x / b);

}

int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int tst=1;
//cin>>tst;
while(tst--)
{
	solve();
}
}

Measured memory_bytes: 3664
#include<iostream>

using namespace std;

int main(){
  int lst[100]={0};
  int N;
  int al,am;
  long long sum = 0;
  cin >> N;
  for(int i = 1;i <= N;i++){
    if(i < 10){am = i;}
    else if(i < 100){am = i/10;}
    else if(i < 1000){am = i/100;}
    else if(i < 10000){am = i/1000;}
    else if(i < 100000){am = i/10000;}
    else{am = i/100000;}
    al = i%10;
    lst[al*10+am]++;
  }
  for(int i = 1;i <= N;i++){
    if(i < 10){am = i;}
    else if(i < 100){am = i/10;}
    else if(i < 1000){am = i/100;}
    else if(i < 10000){am = i/1000;}
    else if(i < 100000){am = i/10000;}
    else{am = i/100000;}
    al = i%10;
    sum += (long long)lst[am*10+al];
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<time.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
int main(){
	int n;
	cin>>n;
	while(n--){
		string s="";
		string in;
		cin>>in;
		s+=in[0];
		int q=0;
		int qq=1;
		while(in.size()!=qq){
			if(in[qq]=='<'){
				qq+=2;
				if(q)q--;
				else s.insert(s.begin(),in[qq]);
			}else{
				qq+=2;
				if(q!=s.size()-1)q++;
				else {s+=in[qq];q++;}
			}
			qq++;
		}
		cout<<s<<endl;
	}
}

Measured memory_bytes: 1228
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;

int main(){
    int companies[2001][2], n, d;
    string in;
    memset( companies, 0, sizeof(companies) );
    while( getline(cin, in) ){
        if( in.length() == 0 )  break;
        sscanf( in.c_str(), "%d,%d", &n, &d );
        companies[n][0]++;
    }
    while( getline(cin, in) ){
        sscanf( in.c_str(), "%d,%d", &n, &d );
        companies[n][1]++;
    }
    for( int i=0; i<=2000; i++ ){
        if( companies[i][0] && companies[i][1] ){
            printf("%d %d\n", i, companies[i][0]+companies[i][1]);
        }
    }
    return 0;
}

Measured memory_bytes: 1260
/*
#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::cpp_int mint; //*/
#include <bits/stdc++.h>
#define  rep(i,n) for(li i=0;i<(n);i++)
#define  red(i,n) for(li i=(n)-1;i>=0;i--)
#define  all(a) begin(a),end(a)
#define  pb(a) push_back(a)
using namespace std;
typedef long int li;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<li> vli;
typedef vector<string> vs;
 
int main()
{
    int n;
    cin>>n;
    int a[n],ans=0,q=0;
    bool x[n]={0};
    rep(i,n)cin>>a[i];
    while(q!=1) {
        if(x[q]) cout<<-1<<endl,exit(0);
        x[q]=1;
        q=a[q]-1;
        ans++;
    }
    cout<<ans<<endl;    

    return 0;
}

Measured memory_bytes: 768
#define _GLIBCXX_DEBUG
#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=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second


int main() {
    
    int n,m;cin >> n >> m;
    if(n==m)cout << "Yes" << endl;
    else cout << "No" << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include <string>
#include <stack>
#include<stdio.h>
#include <queue> 
#include <functional>
#define rep(i,n) for (int i=0; i < (int)(n); i++)

using namespace std;

int main(){
	
	stack<int> st; // スタックを宣言＋初期化
	
	int i,j,k;
	int arr[100];
	string str;
	stack<int> intStack; // 整数値を格納するスタックを宣言
    stack<string> strStack; // 文字列を格納するスタックを宣言	
	queue<int> ique; // 整数値を格納するキューを宣言
	
	while(1){
		int a=0,b=0,c=0,d=0,e=0,num;
	cin >> num;
	
	if (num==0) return 0 ;
	
	rep(i , num){
		
		cin >>  a >> b ;
		
		if(a < b ) d += a + b;
		else if(b < a) c+= a+ b;
		else{
			c+= a;
			 d+=a;
		}
		 
	}
	
	cout << c << " " << d << endl;
	}
		
	return 0;
		
}

Measured memory_bytes: 0
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  int n,k; cin >> n >> k;
  vector<bool> ans(n);
  rep(i,k){
    int d; cin >> d;
    rep(i,d){
      int a; cin >> a; a--;
      ans[a]=1;
    }
  }
  int sum=0;
  rep(i,n){
    if(ans[i]==0) sum++;
  }
  cout << sum << endl;
}

Measured memory_bytes: 3624
import sys
sys.setrecursionlimit(500000)

N = int(input())
A = []

for _ in range(2):
    *line, = map(int, input().split())
    A.append(line)

def dfs(h, w):
    if h<0 or w<0 or h>=2 or w>=N:
        return 0
    if h==0 and w==0:
        return A[h][w]
    ret = max(dfs(h-1, w)+A[h][w], dfs(h, w-1)+A[h][w])
    return ret

print(dfs(1, N-1))


Measured memory_bytes: 3064
import java.util.*;
public class Main{
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                long[] yono = new long[n + 1];
                yono[0] = 2;
                yono[1] = 1;
                for(int i = 2 ; i <= n ; i++){
                        yono[i] = yono[i - 1] + yono[i - 2];
                }
                System.out.println(yono[n]);
                sc.close();
        }
}//0=48
//鶏になれ

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

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;
const int MAX_E = 2000;
const int MAX_N = 1000;

struct UF{
	int par[MAX_N];
	int rank[MAX_N];
	int si[MAX_N];

	void init(int n){
		rep(i,n){
			par[i] = i;
			rank[i] = 0;
			si[i] = 1;
		}
	}

	int find(int x){
		if(par[x] == x) return x;
		else return par[x] = find(par[x]);
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
			si[y] += si[x];
		} else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
			si[x] += si[y];
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
} uf;

struct edge{ ll u, v, cost; };
bool comp(const edge& e1, const edge& e2){
	return e1.cost < e2.cost;
}

ll pow2[10000];
edge es[MAX_E];
int n, m;
ll x;
int useEdge = -1;
int unUseEdge = -1;

ll kruskal(){
    uf.init(n);
	ll res = 0;
    if (useEdge != -1) {
        uf.unite(es[useEdge].u, es[useEdge].v);
        res += es[useEdge].cost;
    }
	for(int i = 0; i < m; i++){
        if (i == unUseEdge) continue;
		edge e = es[i];
		if(!uf.same(e.u, e.v)){
			uf.unite(e.u, e.v);
			res += e.cost;
		}
	}
	return res;
}

int main() {
    pow2[0] = 1;
    for (int i = 1; i < 10000; i++) pow2[i] = pow2[i-1]*2%MOD;
    cin >> n >> m;
    cin >> x;
    rep(i,m) {
        int u, v; ll w;
        cin >> u >> v >> w;
        u--; v--;
        es[i].u = u;
        es[i].v = v;
        es[i].cost = w;
    }
	sort(es, es+m, comp);
    ll all_kru = kruskal();
    if (all_kru == x) {
        ll X = 0, Y = 0;
        rep(i,m) {
            useEdge = i;
            ll now_kru = kruskal();
            if (now_kru == x) {
                X++;
            } else {
                Y++;
            }
        }
        cout << pow2[Y]*(pow2[X]-2+MOD)%MOD << endl;
    } else {
        ll X = 0, Y = 0;
        rep(i,m) {
            useEdge = i;
            ll now_kru = kruskal();
            if (now_kru == x) {
                Y++;
            } else if (now_kru > x) {
                X++;
            }
        }
        cout << pow2[X]*(pow2[Y]-1+MOD)*2%MOD << endl;
    }
}
































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

int main(){
	int a,b;
	string s;
	cin>>a>>b>>s;
	if(s[a]=='-'){
		for(int i=0;i<a;i++){
			if(s[i]-'0'<0||s[i]-'0'>10){
				cout<<"No"<<endl;
				return 0;
			}
		}
		for(int i=a+1;i<=a+b;i++){
			if(s[i]-'0'<0||s[i]-'0'>10){
				cout<<"No"<<endl;
				return 0;
			}
		}
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256