akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long int> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long int>> vvl;
typedef pair<int, int> pii;
typedef pair<long long int, long long int> pll;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long int, long long int>> vll;
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define test() long long int t; cin >> t; cin.ignore(); while(t--) 
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define MOD 1000000007
#define SMOD 998244353
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sp " "
#define inp(a) ll a;cin>>a;cin.ignore()
#define inps(a,b) ll a,b;cin>>a>>b;cin.ignore()
#define out(a) cout<<SP(20)<<a<<'\n'
#define outs(a,b) cout<<SP(20)<<a<<" "<<b<<'\n'
#define ins insert
#define er erase
#define lb lower_bound
#define ub upper_bound
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define inpa(a,n) ll a[n]; for(int i=0; i<n; i++){cin>>a[i];}
#define inpv(a,n) vl a; for(int i=0; i<n; i++){inp(x);a.pb(x);}
#define outa(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<'\n';
#define outv(v) for(auto i:v){cout<<i<<" ";}cout<<'\n';
set<char> vow = {'a','e','i','o','u','A','E','I','O','U'};
bool check1;
ld xpow(ld n, ll m){if(m==0){return 1;}else{ld x = xpow(n, m/2);if(m&1){ld res = x*x*n;if(res>1e7){check1=1;};return res;}else{ld res = x*x;if(res>1e7){check1=1;}return res;}}}
ll xmod(ll a, ll m){return (((a%m)+m)%m);}
ll xmodpow(ll n, ll m, ll y){if(m==0){return 1;}else{ll x = xmodpow(n, m/2, y);if(m&1){return xmod((xmod((xmod(x,y)*xmod(x,y)),y)*xmod(n,y)),y);}else{return xmod((xmod(x,y)*xmod(x,y)),y);}}}
 
int main(){
    fast();
 
/* you get what you work for not what you wish for */
    
    inp(n);
    map <ll, pll> m;
    vl a;
    for(int i=0; i<n; i++){
        a.pb(i);
        inps(x, y);
        m[i] = {x, y};
    }
    ld sum = 0;
    ld cnt = 0;
    do{
        for(int i=1; i<n; i++){
            pll x = m[a[i-1]];
            pll y = m[a[i]];
            ld z = xpow(x.ff-y.ff, 2);
            ld zz = xpow(x.ss-y.ss, 2);
            z+=zz;
            sum += sqrt(z);
        }
        cnt++;
    }while(next_permutation(all(a)));
    sum/=cnt;
    cout << SP(30) << sum << endl; 
}

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

int main() { 
    int n, h, a, b, a_max = 0, ans = 0;
    cin >> n >> h;
    vector<pair<int, int>> v;
    vector<int> nageru;
    for(int i = 0; i < n; ++i) {
        cin >> a >> b;
        a_max = max(a_max, a);
        v.push_back(make_pair(a, b));
    }

    for(int i = 0; i < v.size(); ++i) {
        if(v[i].second > a_max) {
            nageru.push_back(v[i].second);
        }
    }

    sort(nageru.begin(), nageru.end(), greater<int>());

    for(int i = 0; i < nageru.size(); ++i) {
        if(h > 0) {
            h -= nageru[i];
            ans++;
        } else {
            cout << ans << '\n';
            return 0;
        }
    }

    ans += (h + (a_max - 1))/a_max;

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 1908
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int P = 998244353;
int n;
string s;
int il[3];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n >> s;
  int res = 1;
  for(auto z:s){
    int el;
    if(z == 'R')el = 0;
    else if(z == 'G')el = 1;
    else el = 2;
    vector<int> pom;
    R(i,3){
      cerr << il[i] << " ";
      if(il[i] > il[el]){
        pom.PB(il[i]);
      }
    }
    cerr << "---" << res << "\n";
    sort(ALL(pom));
    debug(pom);
    if(SZ(pom)){
      res = res * (pom[0] - il[el]) % P;
    }
    il[el]++;
  }
  R(i,n){
    res = res * (i + 1) % P;
  }
  cout << res << "\n";
}


Measured memory_bytes: 720
#include <iostream>
using namespace std;
long int n;
long long bCount[100001];
long int a[100001];
long int b[100001];
long int c[100001];

void quickSort(long int arr[], long int left, long int right) {
    long int i = left, j = right;
    long int tmp;
    long int pivot = arr[(left + right) / 2];
    
    /* partition */
    while (i <= j) {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };
    
    /* recursion */
    if (left < j)
        quickSort(arr, left, j);
    if (i < right)
        quickSort(arr, i, right);
}

void read(long int arr[]) {
    for (long int i=0; i<n; i++) {
        cin >> arr[i];
    }
}

void calculateBCount() {
    long int cPos = n-1;
    bCount[n] = 0;
    
    for (long int i=n-1; i>=0; i--) {
        
        while (cPos>=0 && b[i]<c[cPos]) {
            cPos -= 1;
        }
        
        bCount[i] = bCount[i+1] + (n-cPos-1);
    }
    
}

long long calculateresult() {
    long int bPos = n-1;
    long long sum = 0;
    
    for (long int i=n-1; i>=0; i--) {
        
        while (bPos>=0 && a[i]<b[bPos]) {
            bPos -= 1;
        }
        
        sum = sum + bCount[bPos+1];
    }
    
    return sum;
}

int main(int argc, const char * argv[]) {
    
    cin >> n;
    read(a); quickSort(a, 0, n-1);
    read(b); quickSort(b, 0, n-1);
    read(c); quickSort(c, 0, n-1);
    
    calculateBCount();
    
    cout << calculateresult();
    
    return 0;
}

Measured memory_bytes: 3328
N, K = map(int, input().split())
S = input()

l = [0]
curr = '1'
for c in S:
    if c != curr:
        l.append(1)
        curr = c
    else:
        l[-1] += 1
if curr == '0':
    l.append(0)

n_group = len(l) // 2
sum_ = 0
k = min(K, n_group)
for i in range(k):
    sum_ += l[2*i] + l[2*i+1]
sum_ += l[2*k]
max_ = sum_
for i in range(k, n_group):
    sum_ -= l[2*i-2*K] + l[2*i+1-2*K]
    sum_ += l[2*i+1] + l[2*i+2]
    max_ = max(max_, sum_)
print(max_)


Measured memory_bytes: 4088
An = sorted(list(map(int,input().split())))
ans = 0
coslist = []
for i,a in enumerate(An):
    if i ==0:
        coslist.append(abs(a-i))
    else:
        ans+=abs(a-(An[i-1]))
        coslist.append(abs(a-(An[i-1])))
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, k;
ll ans;
map<int, int> M;
ll norm(ll x) { return (x % k + k) % k;}
ll a[maxn];
int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] += a[i - 1];
	M[0] = 1;
	for(int i = 1; i <= n; ++i) 
	{
		a[i] = norm(a[i] - i);
		if(i >= k) --M[a[i - k]]; 
		ans += M[a[i]];
		++M[a[i]];
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 11136
import java.util.*;

public class Main {

    static final int MOD = 1000000007;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        if(s[0]==s[1]&&s[1]==s[2]||s[1]==s[2]&&s[2]==s[3]) System.out.println("Yes");
        else System.out.println("No");


    }
}


Measured memory_bytes: 23892
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
#define w(x) int x; cin>>x; while(x--)
ll int n,k;
int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    ll int mod=1e9+7;
    ll int ans1=1,ans2=1,ans3=1;
    for(int i=0;i<n;i++)
    {
        ans1=ans1*10;   ans1%=mod;
        ans2=ans2*9;    ans2%=mod;
        ans3=ans3*8;    ans3%=mod;
    }
    ll int ans_final=(ans1-2*ans2+ans3+mod)%mod;
  	while(ans_final<0)
      ans_final+=mod;
    cout<<ans_final;
}

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

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef int64_t Int;
typedef std::vector<Int> LI;
const double pi = 3.14159265358979323846264338;
const Int mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(Int& x) { if( scanf("%" PRId64, &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
template<> void scan1(LI& xs) { for(Int &x : xs) scan1(x); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

template<typename T>
struct Maybe {
   T x;
   bool valid;
   Maybe() : valid(false) {}
   Maybe(T x_) : x(x_), valid(true) {}
   operator T() const {
      assert( valid );
      return x;
   }
};

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void solve() {
      Int n, z, w; scan(n, z, w);
      std::vector<Int> xs(n); scan(xs);
      Int max = std::abs(w - xs.back());
      for(Int i = 0; i < n - 1; ++i) {
         Int min = std::abs(xs[i] - xs.back());
         for(Int k = i + 1; k < n - 1; ++k) {
            Int score = std::abs(xs[k] - xs.back());
            min = std::min(min, score);
         }
         max = std::max(max, min);
      }
      printf("%ld\n", max);
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}




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

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

    def unite(self, u, v):
        u = self.find(u)
        v = self.find(v)

        if u == v:
            return

        if self.parents[u] > self.parents[v]:
            u, v = v, u

        self.parents[u] += self.parents[v]
        self.parents[v] = u

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

    def same(self, u, v):
        return self.find(u) == self.find(v)

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(N):
    ans = max(ans, uf.size(i))

print(ans)

Measured memory_bytes: 14372
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#pragma region Macros
#define int long long
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define LAST(x) x[x.size()-1]
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
double LOG(int a, int b) {
	return log(b) / log(a);
}
inline bool BETWEEN(int x, int min,int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}

using namespace std;
#pragma endregion
signed main() {
	string s;
	cin >> s;
	cout << s.insert(4, " ")<<endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.Map.Entry;
 
 
 class Main {
	 static int mod =  (int) (Math.pow(10,9)+7);
	 static List<ArrayList<Integer>>  list = new ArrayList<ArrayList<Integer>>();
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        
        String T1 = S.substring(0,N/2);
        String T2 = S.substring(N/2);

        if(T1.equals(T2)) {
            System.out.println("Yes");        	
        } else {
            System.out.println("No");        	        	
        }
                		
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define N 200100
#define mod 1000000007
#define MOD 998244353
#define fn(i,n) for(int i=0;i<n;i+=1)
#define rep(i,l,r) for(int i=l;i<=r;i+=1)
#define INF 100000000000000000
#define pii pair<int,int>
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
vector <int> vis[101];
signed main()
{
    
    speed
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)vis[i].clear();
    for(int i=1;i<=k;i++){
    	int d;cin>>d;
    	for(int j=1;j<=d;j++){
    		int x;cin>>x;
    		vis[x].pb(i);
    	}
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
    	if(vis[i].size()==0)cnt++;
    }
    cout<<cnt<<endl;

    

 
    return 0;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

ll m[200005];
vector<ll> memo(200005, -1);

ll choose(ll n, ll a) {
  ll x = 1, y = 1;
  REP(i,a) {
    x *= n-i;
    y *= i+1;
  }
  return x / y;
}

int main() {
  int n; cin >> n;
  vector<int> a(n);
  REP(i,n) {
    cin >> a[i];
    m[a[i]]++;
  }
  ll ans = 0;
  ll max = 0;

  REP(i, n) {
    if (memo[a[i]] >= 0) continue;
    memo[a[i]] = choose(m[a[i]], 2);
    max+=memo[a[i]];
  }

  REP(i,n) {
    ll x = memo[a[i]];
    if (x <= 0) ans = max;
    else ans = max - x + choose(m[a[i]]-1, 2);
    COUT(ans);
  }
  return 0;
}

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

int main(void){
  string s;
  cin >> s;
  if((s[0]=='Y')&&(s[1]=='A')&&(s[2]=='K')&&(s[3]=='I')){
    cout << "Yes" << endl;
  }
  else cout << "No" <<endl;
  return 0;
}


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

public class Main {
	public static void main(String args[]) throws InterruptedException {
		    Scanner sc = new Scanner(System.in);	
			
			String n = sc.next();
			int[] ar = new int[n.length()-2];
			int ans = 10000;
			for (int i = 0; i < n.length()-2; i++) {
				ar[i] = Integer.parseInt(n.substring(i,i+3));
			}

			for (int i = 0; i < n.length()-2; i++) {
				ans  = Math.min(ans, Math.abs(ar[i]-753));
			}
			System.out.println(ans);

		    sc.close(); }

	public static boolean isEven(int n ) {
		if (n % 2 == 0) {
			return true;
		}else{
			return false;
		}
	}
}

Measured memory_bytes: 21844
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ff first
#define ss second
#define ll long long
#define vi vector<int>
#define vii vector<vi>
#define vs vector<string>
#define vss vector<vs>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, n) for (ll i = (a); i < (n); ++i)
#define repr(i, a, n) for (ll i = (n); i >= (a); --i)
using namespace std;
const int INF(1 << 30);
const ll LLINF(1LL << 55LL);
const int pi = 3.1415926536;
const int MOD = 1000000007;
const int MAX = 510000;

void Main() {
  int x, y, z;
  cin >> x >> y >> z;
  int ans = 0;
  do {
    x = x - y - z;
    ans++;
  } while (y + 2 * z <= x);
  cout << ans << endl;
}

int main() {
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // CとC++の入出力出力を非同期
  std::cout << std::fixed << std::setprecision(15);  // 小数を10進数表示
  Main();
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    D=[int(_) for _ in input().split()]
    dc=Counter(D)
    mod,ans=998244353,1
    if D[0]!=0 or dc[0]!=1:
        print(0)
        sys.exit()
    for i,_ in enumerate(list(dc.items())):
        if i>1:
            ans*=dc[i-1]**dc[i]%mod
    print(ans%mod)

if __name__=='__main__':
    main()

Measured memory_bytes: 21460
import itertools

n, m, q = map(int, input().split())

alist = [list(map(int,input().split())) for i in range(q)]

comb = list(set(itertools.combinations_with_replacement(range(1, m + 1), n)))

# print(comb)

res = 0

for c in comb:
    tmp_score = 0
    for a in alist:
        if c[a[1]-1] - c[a[0]-1] == a[2]:
            tmp_score += a[3]
    res = max(res, tmp_score)

print(res)

Measured memory_bytes: 25612
#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL dp[410][410], sum[410];
LL a[410], n;

LL solve(int l, int r) {
	if(l == r) return 0;
	LL &ret = dp[l][r];
	if(ret != -1) return ret;
	ret = 1000000000000000;
	for(int i = l; i <= r; i++) {
		ret = min(ret, solve(l, i) + solve(i+1, r) + sum[r] - sum[l-1]);
	}
	return ret;
}

int main() {
	memset(dp, -1, sizeof(dp));
	cin>>n;
	for(int i = 1; i <= n; i++) cin>>a[i], sum[i] += sum[i-1] + a[i];
	LL ans = solve(1, n);
	cout<<ans<<endl;
	return 0;
}


// 10 20 30 40
// 30 30 40 ans: 30
// 60 40 ans: 90
// 100 ans: 190

// 10 10 10 10 10
// 20 10 10 10 ans: 20
// 20 20 10 ans: 40
// 20 30 ans: 70
// 50 ans: 120

Measured memory_bytes: 1536
X, Y, A, B, C = map(int, input().split())
Alist = list(map(int, input().split()))
Blist = list(map(int, input().split()))
Clist = list(map(int, input().split()))
Alist.sort(reverse=True)
Blist.sort(reverse=True)
Clist.sort(reverse=True)
W = list()
for i in range(X):
    W.append(Alist[i])
for i in range(Y):
    W.append(Blist[i])
W.sort()
for i in range(min(X+Y, C)):
    if W[i] < Clist[i]:
        W[i] = Clist[i]
    else:
        break
print(sum(W))

Measured memory_bytes: 23328
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define lb lower_bound
#define ub upper_bound
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
const ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}



signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll n,d,a,ans=0;cin>>n>>d>>a;

  V<PL> v(n);
  queue<PL> q;

  rep(i,0,n){
    cin>>v[i].fs>>v[i].sc;
  }
  sort(all(v));

  ll dam=0,now;
  rep(i,0,n){
    now=v[i].fs;
    while(q.size() && q.front().fs<now){
      dam-=q.front().sc;
      q.pop();
    }

    v[i].sc-=dam;
    if(v[i].sc>0){
      ans+=(a-1+v[i].sc)/a;
      dam+=((a-1+v[i].sc)/a)*a;
      q.push({now+2*d,((a-1+v[i].sc)/a)*a});
    }

  }
  
  cout<<ans<<ENDL;
}
//( ・ __ ・ ) KEEP BEING ORGANIZED
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define ll long long
#define pp pair<ll,ll>
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
using namespace std;
template <typename T>
ll max(ll x, ll y)
{
    return x>y ? x : y;
}
template <typename T>
ll min(ll x, ll y)
{
    return x<y ? x : y;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll a,b;cin >> a >> b;
    string c,d;
    for (int i = 0; i < a; ++i)
    {
        c+='0'+b;
    }
    for (int i = 0; i < b; ++i)
    {
        d+='0'+a;
    }
    if(c<d)cout << c;else cout << d;
    }

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

int main(){
	int n,t; cin>>n>>t;
	vector<int> v(n);
	rep(i,n) cin>>v[i];
	ll sec=t;
	for(int i=1; i<n; i++){
		if(v[i]-v[i-1]<t) sec+=v[i]-v[i-1];
		else sec+=t;
	}
	cout<<sec<<endl;
}

Measured memory_bytes: 3944
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

const ll mod=1e9+7;
ll mu(ll a,ll b){
  return (ll)a*b%mod;
}
ll ad(ll a,ll b){
  if((a+=b)>=mod)a-=mod;
  return a;
}
ll pw(ll a,ll b,ll c=1LL){
  for(;b;b>>=1,a=mu(a,a))if(b&1)c=mu(c,a);
  return c;
}
ll dv(ll a,ll b){
  return mu(a,pw(b,mod-2));
}


int main(){

  //i桁目まで決まっている数のうち13でわって0-12余る場合の数
  string s;
  cin >> s;
  int n=s.size();
  int dp[n+1][13];
  rep(j,n+1){
    rep(i,13) dp[j][i]=0;
  }  
  dp[0][0]=1;
  int teisu=1;
  for(int i=n; i>=1; i--){
    if(i!=n) teisu=(teisu*10)%13;
    if(s[i-1]=='?'){
      rep(j,10){
	int t=(teisu*j)%13;
	rep(k,13){
	  dp[n-i+1][(k+t)%13] = ad(dp[n-i+1][(k+t)%13] ,dp[n-i][k]);
	}
      }
    }
    else{
      int kazu=s[i-1]-'0';
      //      cout << kazu << endl;
      int t=(teisu*kazu)%13;
      rep(k,13){
	dp[n-i+1][(k+t)%13] =ad(dp[n-i+1][(k+t)%13] ,dp[n-i][k]);
      }
    }
  }
  //  rep(k,13) cout <<k <<  " amari " << dp[n][k] << endl;
  cout << dp[n][5] << endl;





  
  return 0;

}


Measured memory_bytes: 5504
def main():
    N = int(input())
    *a, = map(int, input().split())

    ctr = [0] * N
    for x in a:
        ctr[x - 1] += 1
    print(*ctr, sep='\n')


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()


Measured memory_bytes: 32380
#include "bits/stdc++.h"

#define rep(i, a) for (int i = 0; i < (a); ++i)
#define REV(i, a) for (int i = (a - 1); i >= 0; --i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

void Main() {
  int n;
  cin >> n;
  vector<P> lr;
  int p, q;
  ll lp = 1, rq = 1000000000;
  ll mx_len = 0;
  rep(i, n) {
    ll l, r;
    cin >> l >> r;
    r++;
    lr.emplace_back(l, r);
    lp = max(lp, l);
    rq = min(rq, r);
    mx_len = max(mx_len, r - l);
  }
  vector<P> ab;
  rep(i, n)
      ab.emplace_back(max(lr[i].second - lp, 0LL), min(lr[i].first - rq, 0LL));
  sort(ab.begin(), ab.end(), greater<P>());
  vector<ll> ds(n), dt(n);
  ds[0] = ab[0].first;
  REP(i, 1, n) ds[i] = min(ds[i - 1], ab[i].first);
  dt[n - 1] = -ab[n - 1].second;
  for (int i = n - 1; i > 0; --i) dt[i - 1] = min(dt[i], -ab[i - 1].second);
  ll ans = mx_len + max(rq - lp, 0LL);
  rep(i, n - 1) ans = max(ans, ds[i] + dt[i + 1]);
  cout << ans << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 4976
#include <iostream>
#include<iomanip>
using namespace std;
int main(void){
   int a,b;
   cin >>a;
   cin>>b;
   int d=a/b;
   int r=a%b;
   double f=double(a)/double(b);
   cout<<d;
   cout<<" ";
   cout<<r;
   cout<<" ";
   cout<<fixed<<setprecision(5)<<f;
   cout<<endl;// Your code here!
    
}


Measured memory_bytes: 3256
#include<stdio.h>

void minheap_insert(int value,int heap[],int counter) //counterは0からスタート
{
  int spot=counter;
  while(spot != 0 && heap[(spot-1)/2] > value)
    {
      heap[spot] = heap[(spot-1)/2];
      spot = (spot-1)/2;
    }
  heap[spot] = value;
}

int minheap_delete(int heap[],int counter) //counterは要素数-1からスタート
{
  int spot=0,temp,re;
  re = heap[spot];
  heap[spot] = heap[counter];
  while(1)
    {
      if(spot*2+2 < counter)
	{
	  if(heap[spot*2+2] < heap[spot*2+1])
	    {
	      if(heap[spot] > heap[spot*2+2])
		{
		  temp = heap[spot];
		  heap[spot] = heap[spot*2+2];
		  heap[spot*2+2] = temp;
		  spot = spot*2+2;
		  continue;
		}
	    }
	}
      if(spot*2+1 < counter && heap[spot] > heap[spot*2+1])
	{
	  temp = heap[spot];
	  heap[spot] = heap[spot*2+1];
	  heap[spot*2+1] = temp;
	  spot = spot*2+1;
	}
      else
	{
	  break;
	}
    }
  return re;
}


int main(void)
{
  int n,i,ans_low,ans_high,tail,lost;
  scanf("%d",&n);
  int array[n],heap[n];
  for(i=0;i<n;i++)
    {
      scanf("%d",&array[i]);
      minheap_insert(array[i],heap,i);
    }
  tail = n-1;;
  for(i=0;i<n;i++)
    {
      if(i == n/2-1)
	{
	  ans_low = minheap_delete(heap,tail);
	}
      else if(i == n/2)
	{
	  ans_high = minheap_delete(heap,tail);
	}
      else
	{
	  lost = minheap_delete(heap,tail);
	}
      tail--;
    }
  for(i=0;i<n;i++)
    {
      if(array[i] <= ans_low)
	{
	  printf("%d\n",ans_high);
	}
      else if(array[i] >= ans_high)
	{
	  printf("%d\n",ans_low);
	}
    }
  return 0;
}


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

#define REP(i, start, count) for(int i=(start); i<(int)(count); ++i)
#define rep(i, count) REP(i, 0, count)
#define ALLOF(c) (c).begin(), (c).end()

using ll = long long;
using ull = unsigned long long;
using veci = vector<int>;
using vecll = vector<ll>;
using vecull = vector<ull>;

struct Magic {
    ll a;
    ll b;
    ll i;
};

ll H, N;


int main(void) {
    cin >> H >> N;

    vector<Magic> M;

    ll amax = 0;
    rep(i, N) {
        Magic m;
        cin >> m.a >> m.b;
        m.i = i;

        M.emplace_back(m);
        amax = max(amax, m.a);
    }

    vecll DP(H + 1, 100000000);
    DP[0] = 0;

    // DP[i] : i ダメージを与えるための最小コスト
    for (int i = 0; i <= H; ++i) {
        for (int k = 0; k < N; ++k) {
            int next_i = min(i + M[k].a, H); // 使った場合のインデックス
            DP[next_i] = min(DP[next_i], DP[i] + M[k].b); // 今回の魔法使った方がお得な場合は挿げ替え
        }
    }

    cout << DP[H] << endl;
    return 0;
}


Measured memory_bytes: 384
import math
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

def main():
    A,B=mi()

    x_sum = 0
    ev_cnt = 0
    if A % 2 == 0:
        if B%2==0:
            x_sum ^=B
            ev_cnt = B//2-A//2 
        else:
            ev_cnt = math.ceil(B/2)-A//2 
             
    else:
        if B%2==0:
            x_sum ^=B
            x_sum ^= A
            ev_cnt = B//2-math.ceil(A/2)
        else:
            x_sum ^= A
            ev_cnt = math.ceil(B/2)-math.ceil(A/2)
    

    if ev_cnt % 2 == 0:
        print(x_sum)
    else:
        print(x_sum^1)

if __name__ == "__main__":
    main()

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

int main()
{
  int t;

  while (cin >> t && t != 0){
    int n;
    int sum = 0;
    cin >> n;
    while (n--){
      int s, f;
      cin >> s >> f;
      sum += (f - s);
    }
    if (sum >= t) cout << "OK" << endl;
    else cout << t - sum << endl;
  }

  return 0;
}

Measured memory_bytes: 1164
H,W=map(int,input().split())
if H%3==0 or W%3==0:
  print(0)
else:
  ans=10000000000000
  h=H//3
  w=W//2
  ptn1=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn1)-min(ptn1))
  
  h=H//3+1
  w=W//2
  ptn2=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn2)-min(ptn2))
  
  h=H//3+1
  w=W//2+1
  ptn3=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn3)-min(ptn3))
  
  h=H//3
  w=W//2+1
  ptn4=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn4)-min(ptn4))
  
  h=H//3
  ptn5=[h*W,(H-h*2)*W]
  ans=min(ans,max(ptn5)-min(ptn5))
  
  h=H//3+1
  ptn6=[h*W,(H-h*2)*W]
  ans=min(ans,max(ptn6)-min(ptn6))

  H,W=W,H
  h=H//3
  w=W//2
  ptn1=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn1)-min(ptn1))
  
  h=H//3+1
  w=W//2
  ptn2=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn2)-min(ptn2))
  
  h=H//3+1
  w=W//2+1
  ptn3=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn3)-min(ptn3))
  
  h=H//3
  w=W//2+1
  ptn4=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn4)-min(ptn4))
    
  h=H//3
  ptn5=[h*W,(H-h*2)*W]
  ans=min(ans,max(ptn5)-min(ptn5))
  
  h=H//3+1
  ptn6=[h*W,(H-h*2)*W]
  ans=min(ans,max(ptn6)-min(ptn6))
  
  print(ans)

Measured memory_bytes: 3192
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int cnt[26];
int main() {
  string s;
  cin >> s;
  
  for(char c : s){
    ++cnt[c - 'a'];
  }
  
  int* it = find(cnt, cnt + 26, 0);
  if(it == cnt + 26){
    cout << "None" << endl;
  }else{
    cout << (char)('a' + (it - cnt)) << endl;
  }
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

void find_divisor(ll N, vector<ll>& divisor) {
  for(int i=1; i<=sqrt(N); i++) {
    if(N % i == 0)
      divisor.push_back(i);
  }
  int n = divisor.size();
  for(int i=n-1; i>=0; i--) {
    if(N != (ll)pow(divisor[i], 2))
      divisor.push_back(N / divisor[i]);
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n; cin >> n;
  vector<ll> div, div2;
  find_divisor(n-1, div);
  find_divisor(n, div2);
  int cnt = 0;
  for(ll d: div2) {
    ll m = n;
    if(d<2) continue;
    while(m>0) {
      if(m==1) {
        cnt++;
        break;
      } else if(m%d) {
        if((m-1)%d==0) cnt++;
        break;
      } else {
        m /= d;
      }
    }
  }
  cout << div.size()-1+cnt << "\n";
  return 0;
}


Measured memory_bytes: 3676
import java.util.*;
import java.util.TreeMap;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String ans = ":(";
    for (int i = 1; i <= N; i++) {
      double A = Math.floor(i * 1.08);

      if (A == N) {
        ans = String.valueOf(i);
        break;
      }
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 22868
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
const ll MAX=1100000;
ll fac[MAX],finv[MAX],inv[MAX];
void COMinit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    repl(i,2,MAX){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k)return 0;
    if(n<0 or k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
int main(){
    COMinit();
    ll N,K;cin>>N>>K;
    ll ans=0;
    repl(i,max(1LL,N-K),N+1){
        ans+=COM(N,i)*COM(N-1,i-1);
        ans%=MOD;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 26112
#include<stdio.h>
int main() {
	int i, j,x,y;
	double tmp=0;
	double index=0;
	scanf("%d %d", &x, &y);
	int m[x];
	double z[x];
	for (i = 0;i < x;i++) {
		scanf("%d", &m[i]);
	}
	for (i = 0;i < x;i++) {
		z[i] = (double)(1 + m[i]) / 2;
	}
	for (i = 0;i < x;i++) {
		tmp += z[i];
		if (i >= y) {
			tmp -= z[i - y];
		}
		if (index < tmp) {
			index = tmp;
		}
	}
	printf("%.12f", index);
	return 0;
}


Measured memory_bytes: 2560
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long 

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    K++;
    cout << (A - B) * ((K % 2 - 1) * 2 + 1) << endl;


    return 0;
}
// A1 = B + C;
// B1 = C + A;
// C1 = A + B;
// A2 = B1 + C1 = C + A + A + B;
// B2 = C1 + A1 = A + B + B + C
// C2 = A1 + B1 = B + C + C + A;

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	for(;;){
		int i,n,m, hito = 0, temp;
		int me[1000];
		int ban[1000];
		
		scanf("%d%d",&n,&m);
		if(n == 0&& m == 0){
			break;
		}
		for(i = 0; i < n; i++){
			scanf("%d",&ban[i]);
		}
		for(i = 0; i < m; i++){
			scanf("%d",&me[i]);
		}
		
		for(i = 0; i < m; i++)
		{
			hito += me[i];
	//		printf("%diÞ\n",me[i]);
			if(hito >= n){
				i++;
				break;
			}
			temp = hito;
	//		printf("øÊÅ%diÞ\n",ban[temp]);
			hito += ban[temp];
			if(hito >= n){
				i++;
				break;
			}
	//		printf("\t¡%d¾æ\n",hito);
		}
		printf("%d\n",i);
	}
}

Measured memory_bytes: 0
import collections

n = int(input())
d = list(map(int, input().split()))

c = collections.Counter(d)

ans = 1

if c[0] != 1 or d[0] !=0:
    ans = 0

for i in range(max(d) + 1):
    if i == 0:
        continue
    ans *= c[i-1] ** c[i]

print(ans%998244353)

Measured memory_bytes: 62252
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  
  int B = 0, E = 0;
  for(int i=0; i<S.size(); i++) {
    if( S.at(i) == 'A' ){
      B = i;
      break;
    }
  }
  for(int i=S.size(); i--;) {
    if( S.at(i) == 'Z' ) {
      E = i;
      break;
    }
  }
  cout << E - B + 1 << endl;
}

Measured memory_bytes: 640
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]

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

if (a == 1):
    a = 14
if (b == 1):
    b = 14

if (a > b):
    print("Alice")
elif (a < b):
    print("Bob")
else:
    print("Draw")



Measured memory_bytes: 9068
#include <cstdio>

using namespace std;

const int C = 26;
const int D = 365;
int c[C];
int s[D][C];
int down[C];

int main() {
    int i, j;
    
    scanf("%*D");
    
    for (i = 0; i < D; i++) scanf("%d", &c[i]);
    
    for (i = 0; i < D; i++) {
        for (j = 0; j < C; j++) {
            scanf("%d", &s[i][j]);
        }
    }
    
    for (i = 0; i < D; i++) {
        int best = -1e9, index = -1;
        
        for (j = 0; j < C; j++) down[j] += c[j];
        
        for (j = 0; j < C; j++) {
            int sum = s[i][j] + down[j];
            
            if (sum > best) {
                best = sum;
                index = j;
            }
        }
        
        printf("%d\n", index + 1);
        
        down[index] = 0;
    }
    
    return 0;
}


Measured memory_bytes: 1772
#include <bits/stdc++.h>
#include <algorithm>
#include <string>

using namespace std;
int main(){

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

    int arr[100000];

    fill_n(arr, 100000, 0); // set all index value to 0
    int i;

    int input;
    long long int sum = 0;
    for(i = 0; i < n; i++){
        scanf("%d", &input);
        arr[input - 1] = arr[input - 1] + 1;
        sum = sum + input;
    }

    int q; scanf("%d", &q);
    int old_val, new_val;

    while(q--){
        scanf("%d", &old_val);
        scanf("%d", &new_val);

        sum = ((new_val - old_val) * arr[old_val - 1]) + sum;
        printf("%lld\n", sum);

        arr[new_val - 1] = arr[new_val - 1] + arr[old_val - 1];
        arr[old_val - 1] = 0;
    }
}


Measured memory_bytes: 4216
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 10000000000000000 //1e16
 
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
 
 
// using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int t,n,m,i,k,r,l,u,v,w,j,s,sum=0,pos,flag=0,count=0;
    string S,T,U; 
    int a,b,c;
    cin>>a>>b>>n;
    m=min(n,b-1);
    cout<<(a*m)/b-a*(m/b);
}
 
 
signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

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

const int MOD = 998244353;
long long dp1[301][90001],dp2[301][90001];

int main() {
  int N;
  long long sum,total;
  cin>>N;
  vector<long long> a(N);
  total = 1;
  sum = 0;
  for (int i = 0; i < N; i++) {
    cin>>a[i];
    sum += a[i];
    total *= 3;
    total %= MOD;
  }
  dp1[0][0] = dp2[0][0] = 1;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j+a[i] <= sum; j++) {
      dp1[i+1][j] = (dp1[i+1][j]+2*dp1[i][j])%MOD;
      dp1[i+1][j+a[i]] = (dp1[i+1][j+a[i]]+dp1[i][j])%MOD;
      dp2[i+1][j] = (dp2[i+1][j]+dp2[i][j])%MOD;
      dp2[i+1][j+a[i]] = (dp2[i+1][j+a[i]]+dp2[i][j])%MOD;
    }
  }
  long long res1,res2;
  res1 = res2 = 0;
  for (int j = sum/2 + 1; j <= sum; j++) {
    res1 = (res1+3*dp1[N][j])%MOD;
  }
  if(sum%2 == 0) {
    res2 = 3*(dp2[N][sum/2]-dp1[N][sum/2]);
  }
  long long ans = 0;
  ans = (total + MOD - res1 + res2)%MOD;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 422784
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
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; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int ans = 0;
    vector<int> v(n);
    rep(i,n) cin >> v[i];
    rep(i,n){
        int c;
        cin >> c;
        if(v[i] > c) ans += v[i] - c;
    }
    cout << ans << endl;
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
using vl = vector<ll>;  // long longの1次元の型に vl という別名をつける
using vvl = vector<vl>; // long longの2次元の型に vvl という別名をつける
int MOD = 1000000007; //10^9 + 7

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 ll  LINF = 1LL << 60;
const int iINF = 1 << 29;

int main(void){
  int a,b,c;
  cin >> a >> b >> c;
  if((a + c == b) || (a + b == c) || (b + c == a))cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3616
n, m = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(m)]

M = [0] * n

for a, b in AB:
  M[a - 1] = max(M[a - 1], H[b - 1])
  M[b - 1] = max(M[b - 1], H[a - 1])

ans = 0
for i, j in zip(H, M):
  if j == 0 or i > j:
    ans += 1

print(ans)

Measured memory_bytes: 32024
#include <stdio.h>

int main(void) {
	int n, i;
	int a[1001];
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++){
		scanf("%d", &a[i]);	
	}
	
	for (i = n-1; i >= 0; i--){
		if (i == 0) printf("%d", a[i]);
		else printf("%d ", a[i]);
	}
	
	printf("\n");
	
	return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	string T;
	if(S=="Sunny"){
		T = "Cloudy";
	} else if(S=="Cloudy"){
		T = "Rainy";
	} else {
		T = "Sunny";
	}

	cout << T << endl;
}

Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  (r : g : b : n : _) <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  let
    list = do
      let r' = n `div` r
      i <- [0..r']
      let g' = (n - r * i) `div` g
      j <- [0..g']
      return $ (n - r * i - g * j) `mod` b
  print . length . filter (== 0) $ list

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 508
def sieve():
    L = 50000
    primes = []
    isPrime = [ True for _ in range(L) ]
    for i in range(2, L):
        if isPrime[i]:
            primes.append(i)
            for j in range(i*i, L, i):
                isPrime[j] = False
    return primes

def isConsecutivePrime(num, idx, primes):
    p = 0
    while True:
        p += primes[idx]
        if p == num:
            return True
        if p > num:
            return False
        idx += 1

def countConsecutivePrimes(num, primes):
    count = 0
    for i in range(len(primes)):
        if isConsecutivePrime(num, i, primes):
            count += 1
    return count

if __name__ == '__main__':
    primes = sieve()
    while True:
        num = int(input())
        if num == 0:
            break
        print(countConsecutivePrimes(num, primes))


Measured memory_bytes: 6024
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

ll mod = 1e9 + 7;

vector<ll> fact;

void init_fact(int n) {
    fact = vector<ll>(n);
    fact[0] = 1;
    for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i % mod;
}

ll calc_pow(ll x, ll pow) {
    if (pow == 0) return 1;
    ll a = calc_pow(x, pow / 2);
    a = a * a % mod;
    if (pow % 2 == 1) a *= x;
    return a % mod;
}

ll calc_div(ll a, ll b) {
    return a * calc_pow(b, mod - 2) % mod;
}

int main() {
    init_fact(200000);

    int n, prev;
    cin >> n >> prev;

    ll prob = 0, ret = 0;
    for (int i = 1; i < n; i++) {
        prob += calc_div(fact[n - 1], i), prob %= mod;

        int now;
        cin >> now;
        ret += (now - prev) * prob, ret %= mod;
        prev = now;
    }

    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include <algorithm> 
using namespace std;

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;

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

    bool flag=false;
    string ms=s;
    do {
        if(ms==t) {
            flag=true;
            break;
        }
        ms= ms.substr(ms.size()-1,1)+ms.substr(0,ms.size()-1);
    } while(ms!=s);
    Yes(flag)
}

Measured memory_bytes: 256
from collections import deque
n,m = map(int,input().split())
path = [set() for _ in range(n)]
pathr= [set() for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    path[a-1].add(b-1)
    pathr[b-1].add(a-1)

def bfs(start):
    que = deque()
    d = [1e100]*n
    for i in path[start]:
        que.append(i)
        d[i] = 1
    while que:
        p = que.popleft()
        for nxt in path[p]:
            if d[nxt] == 1e100:
                que.append(nxt)
            d[nxt] = min(d[nxt], d[p] + 1)
    if d[start] == 1e100:
        return [0] * (n+1)
    ret = [0]*d[start]
    ret[-1] = start
    now = start
    for i in range(d[start] - 1)[::-1]:
        for p in pathr[now]:
            if d[p] == i+1:
                now = p
                ret[i] = now
                break
    return ret
ans = [0]*(n+1)
for i in range(n):
    tmp = bfs(i)
    if len(ans) > len(tmp):
        ans = tmp
if len(ans) > n:
  print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i+1)


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

int N, K, A[100000];

int check(int key)
{
	int i = 0;
	for (int j = 0; j < K; j++)
	{
		int s = 0;
		while (s + A[i] <= key)
		{
			if (i == N) return N;
			s = s + A[i];
			i++;
			
		}
	}
	return i;
}

int solve()
{
	int left = 0;
	int right = 100000 * 10000;
	while (right-left>1)
	{
		int mid = (left + right) / 2;
	//	cout << mid << endl;
		int v = check(mid);
		if (v >= N) right = mid;
		else left = mid;
	}
	return right;
}

int main()
{
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	int ans = solve();
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3480
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#define nmax_def 2200
#define Cmax_def 2200
#define mod 1000000007
using namespace std;
typedef long long ll;

int main() {
	ll i, j;
	ll N, K, A[nmax_def];
	cin >> N >> K;
	ll ans1 = 0;
	ll ans2 = 0;
	for (i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	for (i = 0; i < N; i++)
	{
		for (j = i+1; j < N; j++)
		{
			if (A[i] > A[j])
				ans1++;
		}
	}
	ans1 *= K;
	ans1 %= mod;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (A[i] > A[j])
				ans2++;
		}
	}
	K *= K - 1;
	K /= 2;
	K %= mod;
	ans2 *= K;
	ans2 %= mod;
	ll ans = ans1 + ans2;
	ans %= mod;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256