akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {

    long long N, A, B;
    cin >> N >> A >> B;
    long long diff = B - A;

    if (diff % 2 == 0) cout << diff / 2 << endl;
    else cout << min((A + B - 1) / 2, (2 * N - A - B + 1) / 2) << endl;
    
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
from itertools import accumulate

def solve(N: int, W: "List[int]"):
    #print(W)
    sumL = sum(W)
    sumR = 0
    ans = abs(sumL-sumR)
    for i in range(N):
        sumL -= W[i]
        sumR += W[i]
        ans = min(ans, abs(sumL-sumR))
    print(ans)

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, W)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
# -*- coding: utf-8 -*-
"""
Sliding Window - The Smallest Window II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_B&lang=jp

"""
from collections import defaultdict

N, K = map(int, input().split())
A = [int(a) for a in input().split()]

left, right, num = 0, 0, 0
ans = float('inf')
count = defaultdict(int)
while True:
    while right < N and num < K:
        if count[A[right]] == 0 and A[right] <= K:
            num += 1
        count[A[right]] += 1
        right += 1
    if num < K:
        break
    ans = min(ans, right - left)
    if count[A[left]] == 1 and A[left] <= K:
        num -= 1
    count[A[left]] -= 1
    left += 1
print(ans if ans != float('inf') else 0)



Measured memory_bytes: 20564
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod 100000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;


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

vector<string> field;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int H, W;
bool seen[510][510];

void dfs(int h, int w)
{
    seen[h][w] = true;
    for (int dir = 0; dir < 4;dir++)
    {
            int nh = h + dx[dir];
            int nw = w + dy[dir];
        
        if(nh < 0|| nh >= H || nw < 0 || nw >= W){
            continue;
        }
        if(field[nh][nw] == '#'){
            continue;
        }
        if(seen[nh][nw]){
            continue;
        }
        dfs(nh, nw);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout << fixed << setprecision(15);
    string s;
    cin >> s;
    int count = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if(s[i] == '1'){
            count++;
        }
    }
    cout << count << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define lli long long int
#include <limits.h>
#include <fstream>
#define F first
#define S second
#define PI 3.141592653589793238
#define pb push_back

using namespace std;

//doesn't work for arrays
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

lli gcd(lli a,lli b)
{
    if(a==0)
        return b;
    return (b%a,a);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli i,j,tt=1;
    //cin>>tt;
    while(tt--)
    {
        lli a,b,c,k,ct=0;
        cin>>a>>b>>c>>k;
        while(a>=b)
        {
            b*=2;
            ct++;
        }
        while(b>=c)
        {
            c*=2;
            ct++;
        }
        if(ct<=k)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    
    int y,m,d;
 
    char c1,c2;
 
    cin>>y>>c1>>m>>c2>>d;
 
    if( m > 4) cout<<"TBD"<<endl;
 
    else cout<<"Heisei"<<endl;
 
    return 0;
}

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

int main()
{
	int N = 0, ans = 0;
	std::cin >> N;
	
	std::vector<int> L(N);

	for (int i = 0; i < N; i++)
	{
		std::cin >> L[i];
	}

	std::sort(L.rbegin(), L.rend());

	for (int i = 0; i < N-2; i++)
	{
		for (int j = i + 1; j < N - 1; j++)
		{
			for (int k = j + 1; k < N; k++)
			{
				if (L[i] < L[j] + L[k]){		ans++;	}
				else	{	break;	}
			}
		}
	}

	std::cout << ans << std::endl;

	return 0;
}

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

def main():
    for k in range(K):
        li = [0 for i in range(N+1)]
        rsl = [0 for i in range(N+1)]


        for i in range(N):
            if A[i] != 0:
                li[max(0,i-A[i])]+= 1
                li[min(N,i+A[i]+1)]-= 1
        
        mm = 0
        for i in range(N):
            mm += li[i]
            if A[i]>0:
                A[i] = mm
            else:
                A[i] = mm +1
        # print(A)

        if min(A)>=N:
            break
    print(*A)



main()



    





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

int main(){
  int n, ans = 0;
  cin >> n;
  vector<int> p(n);
  for(int i = 0; i < n; i++)
    cin >> p[i];
  auto est = max_element(p.begin(), p.end());
  *est /= 2;
  for(int i = 0; i < n; i++)
    ans +=p[i];
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower
#include <cmath>

using namespace std;
typedef long long ll;

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


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

        rep2(a,1,10){
                rep(b,10){
                        rep(c,10){
                                int cnt = 10001 * a + 1010 * b + 100 * c;
                                if (A <=cnt && cnt<=B)
                                        ans++;
                        }
                }

        }
        cout << ans << endl;

        return 0;
}


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

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

Measured memory_bytes: 23636
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
ll gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }     //最小公倍数
using Graph = vector<vector<int>>;
ll inf=300000000000000000;
const double PI = 3.14159265358979323846;
int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int cnt=0;
  rep(i,n){
    if(s[i]=='1')cnt++;
  }
  if(cnt==0){
    rep(i,n)cout << 1 << endl;
    return 0;
  }
  int k[n];
  k[0]=1;
  rep(i,n-1){
    k[i+1]=k[i]*2%(cnt+1);
  }
  int p[n];
  p[0]=1;
  if(cnt!=1){
    rep(i,n-1)p[i+1]=p[i]*2%(cnt-1);
  }
  int u=0;
  rep(i,n)if(s[i]=='1')u=(u+k[n-1-i])%(cnt+1);
  int q=0;
  if(cnt!=1)rep(i,n)if(s[i]=='1')q=(q+p[n-1-i])%(cnt-1);
  rep(i,n){
    int y=n-1-i;
    if(s[i]=='1'&&cnt==1){
      cout << 0 << endl;
    }
    else if(s[i]=='1'){
      int w=(q+cnt-1-p[y])%(cnt-1);
      int ans=1;
      while(w){
        ans++;
        int g=0;
        rep(j,20){
          if(w&(1<<j))g++;
        }
        w=w%g;
      }
      cout << ans << endl;
    }
    else{
      int w=(u+k[y])%(cnt+1);
      //cout << u << " " << k[y] << endl;
      //cout << i << " " << w << endl;
      int ans=1;
      while(w){
        ans++;
        int g=0;
        rep(j,20){
          if(w&(1<<j))g++;
        }
        w=w%g;
      }
      cout << ans << endl;
    }
  }
}


Measured memory_bytes: 5312
n = int(input())
t, a =map(int, input().split())
h = list(map(int, input().split()))
d_degree = 100000
ans = 0
for i in range(n):
    degree = t - h[i]*0.006
    if d_degree > abs(a - degree):
        d_degree = abs(a - degree)
        ans = i+1
print(ans)


Measured memory_bytes: 3060
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
if n < m:
    x_distance = [x2 - x1 for x1, x2 in zip(x, x[1:])]
    x_distance.sort()
    print(sum(x_distance[:(m-n)]))
else:
    print(0)


Measured memory_bytes: 13960
#include<stdio.h>
int main()
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	int i,cnt=0;
	for(i=a;i<=b;++i){
		if(c%i==0){
			++cnt;
		}
	}
	printf("%d\n",cnt);
	return 0;
}


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

int main(){
    int a, b;
    cin >> a >> b;
    int p = a+b;
    int s = a-b;
    int ml = a*b;
    int ma = max(p,s);
    ma = max(ma,ml);
    cout << ma << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <string>
#include <complex>
#include <stack>
#include <set>
#include <map>

#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i,n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i,s,n) for (int i = (s); i < (n); i++)
#define allof(c) c.begin(), c.end()
#define partof(c,i,n) c.begin() + (i), c.begin() + (i) + (n)
#define EPS 1e-9
#define INF 1000000000
using namespace std;

typedef complex<int> POINT;
template <class T>
class vevector : public vector<vector<T>>
{
public:
	using vector<vector<T>>::operator []; 
	T& operator [](const POINT &index) { return (*this)[index.real()][index.imag()]; }
};

template <class T> T read() { T t; cin >> t; return t; }
template <> POINT read<POINT>() { int x, y; cin >> x >> y; return POINT(x, y); }
template <class T> vector<T> read(int n) { vector<T> v; REP(i,n) { v.push_back(read<T>()); } return v; }
template <class T> vevector<T> read(int n, int m) { vevector<T> v; REP(i,n) v.push_back(read<T>(m)); return v; }
template <class T> vevector<T> readjag(int n) { vevector<T> v; REP(i,n) v.push_back(read<T>(read<int>())); return v; }
template <class T> void write(const T &t) { cout << t << endl; }
template <class T> void write(const T &t, const T &t2) { cout << t << ' ' << t2 << endl; }

template <class T> void write(const vector<T> &v)
{
	ostringstream ss; 
	for (auto x : v) ss << x << ' ';
	auto s = ss.str();
	cout << s.substr(0, s.length() - 1) << endl;
}

template <class T> string toString(const T &t) { stringstream ss; ss << t; return ss.str(); }

struct _Reader { template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } };
#define READ(t,...) t __VA_ARGS__; _Reader(), __VA_ARGS__
#define countof(a) (sizeof(a)/sizeof(a[0]))
#define COMPARISON(t,a,b) [](const t & a, const t & b) -> bool

// primes //
vector<unsigned char> isPrime;
vector<int> primes;
void initPrimes(int n)
{
	isPrime = vector<unsigned char>(n + 1, true);
	isPrime[0] = isPrime[1] = false;
	FOR(i, 2, n)
	{
		if (!isPrime[i]) continue;
		primes.push_back(i);
		for (int j = i * 2; j <= n; j += i)
			isPrime[j] = false;
	}
}

// iota iterator //
struct iotait
{
	int n;
	iotait(int n = 0) : n(n) { }
	iotait &operator ++() { ++n; return *this; }
	int operator *() { return n; }
};

// start up //
void solve();
int main() { solve(); return 0; }


/// template end ///

void solve()
{
	REP (testcase, INF)
	{
		READ(int, N);
		if (!(N)) { break; }
		
		vevector<int> v = readjag<int>(N + 1);
		vector<int> k = v.back(); v.erase(v.end() - 1);
		
		vector<int> innocent(N);
		for (auto l : k)
		{
			REP(i, N) { innocent[i] |= count(allof(v[i]), l) == 0; }
		}

		if (count(allof(innocent), 0) == 1)
		{
			write(find(allof(innocent), 0) - innocent.begin() + 1);
		}
		else
		{
			write(-1);
		}
	}
}

Measured memory_bytes: 1272
from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N + 1)  # -N ~ +Nまで。0はN番目。
# にぶたん：「答えがX以上か？」
ok, ng = 0, 10 ** 9 + 1
while abs(ok - ng) > 1:
    X = (ok + ng) // 2

    B = [(1 if a >= X else - 1) for a in A]
    B = [0] + list(accumulate(B))

    cnt = 0
    BIT.reset()
    B_sorted = {b: i for i, b in enumerate(sorted(B), start=1)}
    for j, b in enumerate(B):
        cnt += BIT.sum(B_sorted[b])
        BIT.add(B_sorted[b], 1)

    if cnt >= ceil((N * (N + 1)) // 2 / 2):
        ok = X
    else:
        ng = X

print(ok)


Measured memory_bytes: 139140
#include <bits/stdc++.h>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long int ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
const int MOD=1000000007;

bool isPowerOfTwo (ll x)  
{  
    return x && (!(x&(x-1)));  
}
bool isPrime(int n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
}
int highestPowerof2(unsigned int n) 
{ 
    // Invalid input 
    if (n < 1) 
        return 0; 
  
    int res = 1;
    for (int i=0; i<8*sizeof(unsigned int); i++) 
    { 
        int curr = 1 << i; 
        if (curr > n) 
           break; 
  
        res = curr; 
    } 
  
    return res; 
} 
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}       
////////////////////////////////////////////////////////////////////

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);  
  cout.tie(NULL);
  int t=1;
  while(t--)
  {
    ll x;
    cin>>x;
    ll p=100;
    ll ans=0;
    ll amt=100;
    for(ans=1;;ans++)
    {
        ll cc=p*0.01;
        amt=p+cc;
        if(amt>=x)
        break;
        p=amt;
    }
    cout<<ans<<"\n";
  }  
  return 0;
}

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

int N,odd=0,even=0;
int a[100010] = {0};
int main(){
    cin >> N;
    for(int i=0,x; i<N;i++) cin >> x, a[x]++;
    for(int i=0; i<100010; i++) if(a[i]){
        odd += a[i]%2 == 1;
        even += a[i]%2 == 0;
    }
    cout << odd + even - even%2 << endl;
    return 0;
}


Measured memory_bytes: 640
import sys
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    N = int(inputs[0])
    A = string_to_int(inputs[1])
    sum_under = 0
    for i in A:
        sum_under += 1/i
    return 1/sum_under


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(2))
    print(ret)

Measured memory_bytes: 3316
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int l=sc.nextInt();
        int r=sc.nextInt();
        int po=Math.min(r-l+1,2019);
        long ans=100000000;
        for(int i=0;i<po-1;i++){
            for(int j=i+1;j<po;j++){
                long ans2=1;
                ans2=((long)(l+i))*(l+j);
                ans2%=2019;
                ans=Math.min(ans,ans2);
            }
        }
        System.out.println(ans);
    }
}


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

// number of integer solutions to Ax + By <= C and x,y >= 0
long long lattice_cnt(long long A, long long B, long long C) {
	using ll = long long;

	assert(A >= 0 && B >= 0);
	if (C < 0) return 0;

	assert(A > 0 && B > 0);
	if (A > B) std::swap(A, B);
	assert(A <= B);

	ll ans = 0;
	while (A > 0) {
		assert(0 < A && A <= B);

		ll k = B/A;
		ll l = B%A;
		assert(B == k * A + l);

		if (C >= 0) {
			ll f = C/B;
			ll e = C%B / A;
			ll g = C%B % A;
			assert(C == f * B + e * A + g);
			assert(C == (f * k + e) * A + f * l + g);

			// either x + ky <= f*k+e
			// i.e. 0 <= x <= (f-y) * k + e
			// or x >= fk + e + 1 - ky
			// and Ax + (Ak+l) y <= C = (fk + e + 1) A + fl - A + g
			// Let z = x - (fk + e + 1 - ky)
			// Az + A(fk + e + 1 - ky) + Aky + ly <= C = A (fk + e + 1) + fl - A + g
			// Az + ly <= fl - A + g

			ans += (f+1) * (e+1) + (f+1) * f / 2 * k;

			//C = f*l - A + g;
			C -= (f*k + e + 1) * A;
		}
		B = A;
		A = l;
	}
	return ans;
}

// count the number of 0 <= (a * x % m) < c for 0 <= x < n
long long mod_count(long long a, long long m, long long c, long long n) {
	assert(m > 0);
	if (n == 0) return 0;

	a %= m; if (a < 0) a += m;

	long long extraC = c / m; c %= m;
	if (c < 0) extraC--, c += m;
	assert(0 <= c && c < m);

	long long ans = extraC * n;

	long long extraN = n / m; n %= m;
	if (n < 0) extraN--, n += m;
	assert(0 <= n && n < m);

	if (extraN) {
		long long g = __gcd(a, m);
		ans += extraN * ((c + g - 1) / g * g);
		//ans += extraN * (lattice_cnt(m, a+m, (a+m) * (m-1)) - lattice_cnt(m, a+m, (a+m) * (m-1) - c));
	}

	if (n) {
		// we want solutions to 0 <= a(N-1-x) - my < c with 0 <= x <= N-1
		// a * (N-1) >= ax + my > a * (N-1) - c
		ans -= lattice_cnt(m, a+m, (a+m) * (n-1) - c);
	}

	return ans;
}

long long mod_count_range(long long a, long long m, long long clo, long long chi, long long nlo, long long nhi) {
	return mod_count(a, m, chi, nhi) - mod_count(a, m, chi, nlo) - mod_count(a, m, clo, nhi) + mod_count(a, m, clo, nlo);
}

using ll = long long;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int K, Q; cin >> K >> Q;
	vector<ll> D(K+1);
	for (int i = 1; i <= K; i++) cin >> D[i], D[i] += D[i-1];

	ll CYC = D[K];
	while (Q--) {
		ll N, X, M; cin >> N >> X >> M;
		ll ans = 0;
		ll totCnt = 0;
		for (int i = 0; i < K; i++) {
			ll xa = X + D[i];
			ll xb = X + D[i+1];
			xa %= M; xb %= M;
			if (xb <= xa) xb += M;
			assert(xb - xa <= M);
			// how many of k * CYC land so that 0 <= xa + k * CYC % MOD < xb + k * CYC % MOD < M
			// how many of k * CYC land so that -xa <= k * CYC % MOD < M - xb

			ll cnt = (N - (i+1) + K - 1) / K;
			totCnt += cnt;

			ans += cnt * (xb - xa);
			//ll cur = mod_count_range(CYC, M, -xa, M-xb, 0, cnt);
			//ans += cur;
		}
		assert(totCnt == N-1);
		//cout << ans << '\n';
		cout << N-1 - (ans + X%M) / M << '\n';
	}

	return 0;
}


Measured memory_bytes: 384
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

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










int main(){
    int N; std::cin >> N;
    std::vector<int> A(N), B(N), C(N+1), D(N+1);
    for(int i(0); i < N; ++i){
        std::cin >> A[i]; ++C[A[i]];
    }
    for(int i(0); i < N; ++i){
        std::cin >> B[i]; ++D[B[i]];
    }
    for(int i(1); i <= N; ++i){
        if(C[i] + D[i] > N){
            std::cout << "No" << std::endl;
            return 0;
        }
        C[i] += C[i-1]; D[i] += D[i-1];
    }
    std::cout << "Yes\n";

    int x(0);
    for(int i(1); i <= N; ++i){
        chmax(x, C[i] - D[i-1]);
    }
    for(int i(0); i < N; ++i){
        if(i) std::cout << " ";
        std::cout << B[(i + N - x) % N];
    }
    std::cout << std::endl;
    return 0;
}


Measured memory_bytes: 6420
#include <stdio.h>
#include <stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}

Node treeMaximum(Node x){
  while(x->right !=NIL){
    x = x->right;
  }
  return x;

}

Node treeSearch(Node u, int k){
  if(u == NIL || k== u->key){
    return u;
  }
  if(k < u->key){
    return treeSearch(u->left,k);
  }
  else return treeSearch(u->right,k);
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right);
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left ==NIL || z->right ==NIL){
    y =z;
  }
  else {y = treeSuccessor(z);}
  if(y->left != NIL){
    x = y->left;
  }
  else x = y->right;
  if(x != NIL){
    x->parent = y->parent;
  }
  if(y->parent ==NIL){
    root =x;
  }
  else if(y == y->parent->left){
    y->parent->left = x;
  }
  else y->parent->right =x;
  if(y != z){z->key = y->key;}


  }

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while(x !=NIL){
    y = x;
    if(z->key < x->key){
      x=x->left;
    }
    else {x = x->right;}
  }
    z->parent = y;
    if(y==NIL){
      root = z;
    }
      else if(z->key < y->key){
	y->left = z;
      }
      else {y->right = z; }
    }

void inorder(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}
void preorder(Node u){
  if(u != NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 20448
#include <stdio.h>
#define min(p,q)((p)<(q)?(p):(q))
#define max(p,q)((p)>(q)?(p):(q))
int a[3];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int t;
		scanf("%d",&t);
		a[t%3]++;
	}
	int ans=0;
	if(a[1]==0&&a[2]==0)ans=1;
	else{
		for(int i=1;i<=2;i++){
			int k=min(a[i]-1,a[3-i]);
			int b1=a[i]-1-k;
			int b2=a[3-i]-k;
			int temp=1+a[0]+k*2;
			if(b1)temp++,b1--;
			if(b1||b2)temp++;
			ans=max(ans,temp);
		}
	}
	printf("%d\n",ans);
}


Measured memory_bytes: 2144
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

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

int main() {
  int n;
  ll ans = 1;
  cin >> n;
  for (int i = 0; i < n; i++) {
    ll t;
    cin >> t;
    ans = lcm(ans, t);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;

const int mod = 1e9 + 7;

const int nax = 2e5 + 5;
int fac[nax], inv_fac[nax];

int mul(int a, int b) {
    return (ll) a * b % mod;
}
int my_pow(int a, int b) {
    int r = 1;
    while(b) {
        if(b % 2) {
            r = mul(r, a);
        }
        a = mul(a, a);
        b /= 2;
    }
    return r;
}
int my_inv(int a) {
    return my_pow(a, mod - 2);
}

int binomial(int a, int b) {
    if(a < 0 || b < 0 || b > a) {
        return 0;
    }
    return mul(fac[a], mul(inv_fac[b], inv_fac[a-b]));
}

int f(int a, int b) {
    int tmp = binomial(a + b, b);
    //~ debug() << imie(a) imie(b) imie(tmp);
    return tmp;
}

int sub(int a, int b) {
    return (a - b + mod) % mod;
}

int main() {
    fac[0] = inv_fac[0] = 1;
    for(int i = 1; i < nax; ++i) {
        fac[i] = mul(fac[i-1], i);
        inv_fac[i] = my_inv(fac[i]);
    }
    int h, w, n;
    scanf("%d%d%d", &h, &w, &n);
    vector<pair<int,int>> in(n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &in[i].first, &in[i].second);
    }
    sort(in.begin(), in.end(), [&](pair<int,int> a, pair<int,int> b) {
        return a.first + a.second < b.first + b.second;
    });
    // dp[i] - the number of paths to vertex in[i] such that it's the first
    // forbidden vertex
    
    in.emplace_back(h, w);
    
    vector<int> dp(n + 1);
    for(int i = 0; i <= n; ++i) {
        int tmp = f(in[i].first - 1, in[i].second - 1);
        debug() << imie(tmp);
        for(int j = 0; j < i; ++j) {
            if(in[j].first <= in[i].first && in[j].second <= in[i].second) {
                tmp = sub(tmp, mul(dp[j], f(in[i].first - in[j].first, in[i].second-in[j].second)));
            }
        }
        dp[i] = tmp;
    }
    debug() << imie(dp);
    printf("%d\n", dp[n]);
}

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

int main(void) {
    int b, i, j, n, k, min=0;
    cin >> n >> k;
    int x[n];
    for(i=0; i<n; i++) {
        cin >> x[i];
        b=x[i]-k;
        if(b<0)
            b*=-1;
        if(x[i]<b)
            min+=x[i]*2;
        else
            min+=b*2;
    }
    cout << min << endl;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
S=input()
c=0
d=0
for i in range(n-1):
    if S[i]==S[i+1]:
        c+=1
    if S[i]!=S[i+1]:
        d+=1
d=(d+1)//2
print(c+2*d-1 if (d<=k and S[0]!=S[-1]) else c+2*min(d,k))

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

using namespace std;

vector<int> adj[100100];
int n, m, ans;
int dp[100100];

int cal(int u){
    if(!dp[u]){
        for(int v : adj[u]){
            dp[u] = max(dp[u], cal(v));
        }
        dp[u]++;
    }
    return dp[u];
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].push_back(y);
    }
    for(int i = 0; i < n; i++) ans = max(ans, cal(i));
    cout << ans - 1 << '\n';
}

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

typedef long long int llint;

struct Edge {
  int to, cost;
  Edge() {}
  Edge(int to, int cost) : to(to), cost(cost) {}
};
  
vector<Edge> node[100001];
int done[100001];

bool dfs(int idx, int cost);

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

  int l, r, d;
  for(int i = 0; i < m; i++) {
    cin>> l >> r >> d;
    node[l].push_back(Edge(r, d));
    node[r].push_back(Edge(l, -d));
  }

  fill(done, done + 100001, -1145141919);

  bool rec = false;
  for(int i = 1; i <= n; i++) {
    if(node[i].size() > 0 && done[i] == -1145141919) rec |= dfs(i, 0);
    if(rec) break;
  }

  cout<< (rec ? "No" : "Yes") <<endl;

  return 0;
}

bool dfs(int idx, int cost)
{
  if(done[idx] != -1145141919) {
    if(done[idx] != cost) return true;
    else                  return false;
  }
  done[idx] = cost;

  bool rec = false;

  for(int i = 0; i < node[idx].size(); i++) {
    Edge e = node[idx][i];
    rec |= dfs(e.to, cost + e.cost);
  }
  
  return rec;
}


Measured memory_bytes: 13952
#include <bits/stdc++.h>
using namespace std;
int count(int arr[], int n, int len)
{
    int *low = lower_bound(arr, arr + len, n);
    if (low == (arr + len) || *low != n) 
        return 0;   
    int *high = upper_bound(low, arr + len, n);      
        return high - low; 
}
int main()
{
    int n, i, len;
    scanf("%d", &n);
    len = n - 1;
    int arr[n];
    for(i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    sort(arr, arr + len);
    for(i = 1; i < n; i++)
    {
        printf("%d\n", count(arr, i, len));
    }
    printf("0");
    return 0;
}

Measured memory_bytes: 4616
import java.util.*;

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

                
            
        }
		

	}
}


Measured memory_bytes: 42392
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long


int main()
{
	string S[3];
	for (int i = 0; i < 3; i++) cin >> S[i];
	int p[3] = { 0 };
	int player = 0;
	int po = 0;
	while (true) {
		if (p[player] == S[player].size()) {
			cout << (char)(player + 'A') << endl;
			return 0;
		}
		po = p[player];
		p[player]++;
		player = (int)(S[player][po] - 'a');
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define rep(i, n) repl(i, 0, n)
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define CST(x) cout << fixed << setprecision(x)
using ll = long long;
const ll MOD = 1000000007;
const int inf = 1e9 + 10;
const ll INF = 4e18 + 10;
const int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	int a = (n + 999) / 1000;
	cout << a * 1000 - n << endl;
	return 0;
}

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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

signed main(){

	lli n,m;
	cin>>n>>m;

	vector<lli> a(n);
	lli sum=0;
	REP(i,0,n){
		cin>>a[i];
		sum += a[i];
	}

	lli border;
	if(sum%(4*m)==0)border = sum/(lli)(4*m);
	else border= sum/(lli)(4*m) +1;

	sort(a.rbegin(),a.rend());

	lli cnt=0;

	REP(i,0,n){
		if(a[i]>=border){
			cnt++;
		}
		else break;
	}
	if(cnt>=m)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        if(i%3==0||i%5==0)
            continue;
        sum+=i;
    }
    printf("%lld\n",sum);
    return 0;
}


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

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

  vector<long int> L( N );

  int count = 0;

  for( int i = 0; i < N; i++ ) 
    cin >> L.at( i );

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

  for( int i = 0; i < N - 2; i++ ) {
    for( int j = 1; j < N - 1; j++ ) {
      for( int k = 2; k < N; k++ ) {
	if( L.at( i ) + L.at( j ) > L.at( k ) && L.at( j ) + L.at( k ) > L.at( i ) && L.at( k ) + L.at( i ) > L.at( j ) && L.at( i ) != L.at( j ) && L.at( j ) != L.at( k ) && L.at( k ) != L.at( i ) && i < j && j < k) {
	  count++;
     // cout << i + 1 << " " << j + 1 << " " << k + 1 << endl;
	}
      }
    }
  }

  cout << count << endl;
}

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

int main(){
  ll x,y;
  cin>>x>>y;
  if(x*y<0){
    cout<<abs(abs(x)-abs(y))+1<<endl;
  }else{
    if(0<=x&&x<=y){
      cout<<y-x<<endl;
    }else if(x<=y&&y<=0){
      cout<<y-x<<endl;
    }else if(x==0&&y<0){
      cout<<-y+1<<endl;
    }else if(y==0&&x>0){
      cout<<x+1<<endl;
    }else{
      cout<<abs(abs(x)-abs(y))+2<<endl;
    }
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>

using namespace std;

#define sz(a) static_cast<int>((a).size())
#define f first
#define s second
#define els(v) for (auto &el : (v))


#ifdef KIRYA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) {
    cerr << _s << " = " << _h << "\n";
}

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;

    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;

    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

const int64_t INF = static_cast<int64_t>(1e9) + 7;
const int64_t LINF = INF * INF;
const int MAXN = static_cast<int>(1e6) + 17;

void solve() {
    int64_t n;
    cin >> n;
    cout << (n - 1) * n / 2 << '\n';
}

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

    int q = 1;

    for (int i = 0; i < q; ++i) {
        solve();
    }
}


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++)

int main() {
  ll a,b,c;
  cin>>a>>b>>c;
  ll ans;
  if(a%2==0||b%2==0||c%2==0){
    ans=0;
  }else{
    ans=min((a*b),min(b*c,c*a));
  }
  cout<<ans<<endl;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin>>n, n) {
        int now, max;
        cin>>now;
        max=now;
        for(int i=1; i<n; i++) {
            int t;
            cin>>t;
            if(now<=0) now=t;
            else now+=t;
            if(max<now) max=now;
        }
        cout<<max<<'\n';
    }
    return 0;
}

Measured memory_bytes: 3040
#include <bits/stdc++.h>
   
using namespace std;
     
#define PB(x) push_back(x)
#define ALL(x) (x).begin(), (x).end()
#define ALLR(x) (x).rbegin(), (x).rend()
#define MP(x) make_pair(x);
    
#define debug(x) cerr << #x << '=' << x << endl;
#define debug2(x, y) cerr << #x << '=' << x << ' ' << #y << '=' << y << endl;
#define debugn(a) for (int x: a) cerr << x << ' '; cerr << endl;
#define debugm(a, n, m) for (int i = 0; i < n; i++, cout << endl)           \
						for (int j = 0; j < m; j++) cout << a[i][j] << ' ';

#define int long long
     
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef vector<string> vs;
typedef unsigned long long ull;

const int INF = LONG_LONG_MAX;
const int NINF = LONG_LONG_MIN;
const int mmod = 1000000007;

int32_t main()
{
	int a, b;
	cin >> a >> b;
	
	cout << max(a+b, max(a-b, a*b)) << endl;
}
// g++ -Wall -Wextra -Wshadow -fsanitize=undefined 


Measured memory_bytes: 256
N,M=map(int,input().split())
A=[input() for i in range(N)]
B=[input() for i in range(M)]

for X in range(N-M+1):
    for Y in range(N-M+1):
        flag=1
        for x in range(M):
            for y in range(M):
                if B[x][y]!=A[x+X][y+Y]:
                    flag=0
                    break
            if not flag:
                break
        if flag:
            print("Yes")
            exit()
print("No")


Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			cout << v[i][j] << "   ";
		}
		cout << endl;
	}
}


int main(){//
    int H, W, K;
    cin >> H >> W >> K;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1--; y1--; x2--; y2--;
    vector<string> c(H);
    for(int i=0; i<H; i++) cin >> c[i];

    const ll INF = 1e18;
    vector<ll> dist(H*W*4 + 5, INF);
    //xをKで割った切り上げ  に Kを掛けた値を返す
    auto modKceil = [&](ll x){
        ll kiriage = (x + K -1) / K;
        return  kiriage * K;
    };
    // h,w,4の3つの値を1セットとした　idに変換
    auto toID = [&](int h, int w, int dir){
        return  (h*W + w) * 4  + dir;
    };

    

    typedef pair<int ,int> P;
    typedef pair<ll, int> LP;
    priority_queue<LP, vector<LP>, greater<LP>> q;
    //値の更新 と qにemplace する
    auto push = [&](int h, int w, int dir, int x){
        ll id = toID(h, w, dir);
        if(dist[id] <= x ) return;//小さくできない場合は何もしない
        dist[id] = x;//値を更新
        q.emplace(x, id);
    };

    //初期値 4方向分
    for(int dir=0; dir<4; dir++) push(x1, y1, dir, 0); 
    
    const int dh[4] = {-1, 0, 1, 0};
    const int dw[4] = {0, -1, 0, 1};   
    while(!q.empty()){
        ll d = q.top().first;
        ll id = q.top().second;
        q.pop();
        if(dist[id] != d) continue;//更新された時にqに残っている古い情報は何もしない
        int h = id /W/4;
        int w = id/4 % W;
        int dir = id % 4;

        //とりあえず向きが変化したとして，4方向動いてみる
        for(int nv=0; nv<4; nv++) push(h, w, nv, modKceil(d));
        
        //今向いている向きに進む
        int next_h = h + dh[dir];
        int next_w = w + dw[dir];
        if(next_h < 0  ||  H <= next_h) continue;
        if(next_w < 0  ||  W <= next_w) continue;
        if(c[next_h][next_w] == '@') continue;
        push(next_h, next_w, dir, d+1);//値の更新とqにemplaceする
        
    }


    ll ans = INF;
    for(int dir=0; dir<4; dir++){
        ll id = toID(x2, y2, dir);
        ans = min(ans, dist[id]);
    }
    if(ans == INF) ans = -1;
    else ans = modKceil(ans) / K;
    cout << ans << endl;
}


Measured memory_bytes: 44192
#include<iostream>
#include<cstdlib>
#include<utility>
#include<tuple>
#include<string>
#include<vector>
#include<numeric>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
using ll = long long;

int main() {

	ll n, k;

	cin >> n >> k;

	int count = 1;

	ll m = k;

	while (n - m >= 0) {
		m *= k;
		count++;
	}

	cout << count << endl;

	return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
using LL = long long;
using ULL = unsigned long long;


int cnt = 0;
void insertionSort(int *A, int n, int g) {
	for (int i = g; i < n; i++) {
		int v = A[i];
		int j = i - g;
		while (j >= 0 && A[j] > v) {
			A[j + g] = A[j];
			j -= g;
			cnt++;
		}
		A[j + g] = v;
	}
}

void solve() {
	int n; cin >> n;
	vector<int> a(1000000); rep(i, n) cin >> a[i];
	vector<int> g;
	int q = 1;
	while (q <= n) {
		g.push_back(q);
		q = q * 2 + 1;
	}
	reverse(g.begin(), g.end());
	rep(i, g.size()) {
		insertionSort(&a.front(), n, g[i]);
	}

	cout << g.size() << endl;
	rep(i, g.size()) {
		if (i != 0) cout << " "; cout << g[i];
	} cout << endl;
	cout << cnt << endl;
	rep(i, n) cout << a[i] << endl;
}

int main() {

	solve();

	return 0;
}



Measured memory_bytes: 6784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define forr(i,a,n) for (int i = (a); i < (n); ++i)
#define rforr(i,a,n) for (int i = (a); i > (n); --i)
#define ALL(x) x.begin(),x.end()
#define LEN(X) ((int)(X).size())
#define CASET int _T; cin >> _T; forr(caset,0,_T)
#define int ll



signed main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //freopen("input.txt","r",stdin);
    int n; cin >> n;

    vector<pii> a(n); 
    forr(i,0,n) {
        int h; cin >> h;
        a[i] = make_pair(h, i+1);
    }
    sort(ALL(a));
    reverse(ALL(a));

    // dp[i][j] i to the left, j to the right
    vector<vector<int>> dp (n+1, vector<int> (n+1, 0));

    int hap = 0;
    forr(i,0,n+1) {
        forr(j,0,n+1) {
            if (i==0 && j==0) continue;
            if (i+j > n) break;
            if (j > 0) {
                dp[i][j] = max(dp[i][j], dp[i][j-1] + a[i+j-1].first*(n+1 - j - a[i+j-1].second));
            }
            if (i > 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j] + a[i+j-1].first*(a[i+j-1].second - i));
            }
            // cout << i << " " << j << " " << dp[i][j] << '\n';
            hap = max(hap, dp[i][j]);
        }
    }

    cout << hap << '\n';

}


Measured memory_bytes: 34620
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

unsigned int gcd(unsigned int a, unsigned int b) {
    if (b ==0) return a;
    else return gcd(b, a%b);
}

int main() {
    unsigned int N, X, xi, D;
    vector<unsigned int> xn;

    cin >> N >> X;
    for (int i=0; i<N; i++) {
        scanf("%d", &xi);
        xn.push_back(xi);
    }
    xn.push_back(X);

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

    D = xn[1] - xn[0];
    for (int i=1; i<N; i++) D = gcd(xn[i+1] - xn[i], D);

    cout << D << endl;

    return 0;

}


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

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (auto &x : a) {
		cin >> x;
	}
	sort(a.begin(), a.end());
	int ans_n = a.back();
	int k = 0;
	for (int i = 1; i + 1 < n; ++i) {
		if (abs(2 * a[i] - ans_n) < abs(2 * a[k] - ans_n)) {
			k = i;
		}
	}
	int ans_r = a[k];
	cout << ans_n << " " << ans_r << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n,ans=0;
	long long a[200005],b[200005]={};
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		b[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		ans+=(b[i]*(b[i]-1))/2;
	}
	for(int i=0;i<n;i++){
		cout<<ans-((b[a[i]]*(b[a[i]]-1))/2)+(((b[a[i]]-1)*(b[a[i]]-2))/2)<<endl;
	}
  return(0);
}

Measured memory_bytes: 5760
#include <cstdio>
#include <set>

using namespace std;

int main()
{
    int a,b,c;
    while( scanf( "%d %d %d\n", &a, &b ,&c ) != EOF){

        set< int > st = {1,2,3,4,5,6,7,8,9,10};
        st.erase( a );
        st.erase( b );
        st.erase( c );
        int ally = a + b, opponent = c,cnt = 0;
        bool yes = 1;
        for( auto x : st )
        {
            if( x + ally <= 20 )
            {
                cnt++;
            }
        }
        if( cnt < 4 )
        {
            yes = 0;
        }
        cnt = 0;
        for( auto x : st )
        {
            if( x + opponent <= 20 )
            {
                cnt++;
            }
        }
        if( cnt < 5 )
        {
            yes = 0;
        }
        if( yes )
        {
            printf( "YES\n" );
        }
        else
        {
            printf( "NO\n" );
        }
    }
    return 0;
}


Measured memory_bytes: 2576
n=int(input())
a=[int(input()) for i in range(n)]

dp=[0]*10001
dp[a[0]]=1

for i in range(1,n):
    for j in reversed(range(10001)):
        if dp[j]>0 and j+a[i]<=10000:
            dp[j+a[i]]=1
    dp[a[i]]=1

ans=0
for i in range(10001):
    if i%10!=0 and dp[i]>0:
        ans=i
print(ans)


Measured memory_bytes: 40668
s = input()
if s == 'SUN':
    ans = 7
elif s == 'MON':
    ans = 6
elif s == 'TUE':
    ans = 5
elif s == 'WED':
    ans = 4
elif s == 'THU':
    ans = 3
elif s == 'FRI':
    ans = 2
elif s == 'SAT':
    ans = 1
    
print(ans)

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,k,x=0;cin>>a>>b>>k;
  for(int i=min(a,b);i>0;i--){
    if(a%i==0&&b%i==0)x++;
    if(x==k){
      cout<<i<<endl;
      break;
    }
  }
}
      

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

using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using Pint = pair<int, int>;
const ll mod = 1e9+7;

pair<int,int> f(int n) {
  int l = n%10;
  int t = 0;
  while(n) {
    t = n%10;
    n/=10;
  }
  return pair<int,int>(l, t);
}


int main(int argc, char const* argv[])
{
  int n;
  cin>>n;

  map<pair<int,int>, int> m;

  for(int i=1; i<=n; i++) {
    m[f(i)]++;
  }

  ll ans = 0;
  for(int i=1; i<=n; i++) {
    pair<int,int> p = f(i);
    ans += m[pair<int,int>(p.second, p.first)];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256