akhauriyash/Code-Regression huggingface dataset:
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
#include <map>
#include <math.h>

using namespace std;
#include <vector>
#define rep(i,n) for (ll i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define base10_4 10000      //1e4
#define base10_5 100000     //1e5
#define base10_6 1000000    //1e6
#define base10_7 10000000   //1e7
#define base10_8 100000000  //1e8
#define base10_9 1000000000 //1e9

#define MOD 1000000007
#define pb push_back
#define ll long long
#define ld long double
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>

// #include <iomanip>
//  cout << fixed << setprecision(15) << y << endl;

string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 

ll A;
ll B;
ll C;
ll N;
ll M;
ll K;

ll ltmp;
string stmp;
double dtmp;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    char aa;
    cin >> aa;
    if(aa - 'Z' <= 0) cout << "A" << endl;
    else cout << "a"<< endl;


}

Measured memory_bytes: 3648
/*
 *  *s.rbegin()=*(--s.end())
 *   sort(v.rbegin(),v.rend()) = negative of v[i] , sort(v.begin(),v.end())
 *   sort(v.begin()+l_index,v.begin()+r_index+1);
 * 
 *   for(auto &it:v)cin>>it; 
 *   n + n/2 + n/3 + n/4 + n/5 + ........n/n =>n*log(n)
 *   n + n/3 + n/5 + n/7 + n/11+.............=>n*log(log(n))
 *   1 , 3 , 5 , 7 , 9 , 11 , 13 , 15 .......=>gcd( a[i] , a[i+1] , a[i+2] )=1;
 *   2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 ......=>upto 1e6 max diff a[i], a[i+1] ~ 150
 *   Every even integer greater than 2 can be expressed as the sum of two primes.[1]  : https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
 *   printf("%03d\n",k);
 *   scanf("%d/%d/%d",&d,&m,&y);   
 */

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define srt(a) sort(a.begin(),a.end())
#define rsrt(a) sort(a.rbegin(),a.rend())
#define lb(a,b) lower_bound(a.begin(),a.end(),b)
#define ub(a,b) upper_bound(a.begin(),a.end(),b)
#define MOD ((int)(1e9+7))
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define float long double
#define sqrt sqrtl
#define cbrt cbrtl
typedef vector<int> vi;
typedef vector<float> vf;
typedef pair<float,int> fi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<fi> vfi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<string> vs;
vector<int>dx={0,1,0,-1},dy={1,0,-1,0};
long long  gcd(long long  a,long long b)
{
     while (a&&b)a>b?a%=b:b%=a;
     return a+b;
}
const int N=1e5;
vvi G(N+1);
vi B(N+1);
int n,m,ans=0;
void dfs(int I)
{
	B[I]=true;
	for(int i=0;i<(int)G[I].size();i++)
	{
		if(!B[ G[I][i] ])dfs(G[I][i]);
	}
}
int32_t main()
{
	IOS
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;cin>>x>>y>>z;
		G[x].pb(y);
		G[y].pb(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!B[i])
		{
			ans++;dfs(i);
		}
	}
	cout<<ans<<endl;
		
	
}
		


Measured memory_bytes: 9600
#include<iostream>
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

int main(){
    vector<int> v;
    int q;cin>>q;
    int x,y;
    for(int i=0;i<q;i++){
        cin>>x;
        switch(x){
            case 0:
                cin>>y;
                v.push_back(y);
                break;
            case 1:
                cin>>y;
                cout<<v[y]<<endl;
                break;
            case 2:
                v.pop_back();
                break;
        }
    }
}


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

#define ll long long int
ll knapsack(int w[], int v[], vector<vector<ll>> &dp, int n, int W)
{
    if(dp[n][W]!=-1)
        return dp[n][W];
    
        if(n==0 || W==0)
        {
            dp[n][W]=0;
        }
        else
        {
            ll res1 = knapsack(w,v,dp,n-1,W), res2=0;
            if(w[n-1]<=W)
                res2=v[n-1]+knapsack(w,v,dp,n-1,W-w[n-1]);
            dp[n][W]=max(res1,res2);
        }
    return dp[n][W];
}
int main()
{
    int n,W;
    cin>>n>>W;
    int w[n],v[n];
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>v[i];
    }
    vector<vector<ll>> dp(n+1,vector<ll>(W+1,-1));
   cout<<knapsack(w,v,dp,n,W)<<endl;

}

Measured memory_bytes: 82980
#include <cstdio>
#include <algorithm>
#include <functional>
#include <set>

int n;
int S[1<<18];

int main(){
  std::multiset<int, std::greater<int> > S, T;
  scanf("%d",&n);
  for(int i=0;i<(1<<n);i++){
    int x;
    scanf("%d",&x);
    S.insert(x);
  }
  T.insert(*(S.begin()));
  S.erase(S.begin());

  for(int i=0;i<n;i++){
    int tmp[1<<18];
    int t=0;
    auto itr = S.begin();
    for(int x: T){
      while(itr != S.end() && *itr == x) ++itr;
      if(itr == S.end()){
        puts("No");
        return 0;
      }
      tmp[t++] = *itr;
      itr = S.erase(itr);
    }
    if(i != n-1) T.insert(tmp, tmp+t);
  }

  puts("Yes");


  return 0;
}


Measured memory_bytes: 13056
#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 {
#ifndef 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__) << "] "

const int mod = (int) 1e9 + 7;
int main() {
	int n;
	cin >> n;
	vector<long long> v(n);
	long long sum = 0;
	for (long long &i : v) cin >> i;
	vector<long long> suf(n, 0);
	suf[n - 1] = v[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		suf[i] = (v[i] + suf[i + 1] % mod) % mod;
	}
	for (int i = 0; i < n - 1; i++) {
		sum = (sum % mod + suf[i + 1] % mod * v[i] % mod) % mod;
	}
		
	cout << sum << "\n";
}


Measured memory_bytes: 6424
s = input()
n = int(input())

for _ in range(n):
    orders = input().split()
    order = orders[0]
    a = int(orders[1])
    b = int(orders[2])
    if order == 'print':
        print(s[a:b + 1])
    elif order == 'reverse':
        s = s[:a] + ''.join(list(reversed(s[a:b+1]))) + s[b + 1:]
    elif order == 'replace':
        s = s[:a] + orders[-1] + s[b + 1:]


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

int main(){
  int N;
  cin >> N;
  
  int max = 0;
  int count = 0;
  for (int i = 0; i < N;i++){
    int H;
    cin >> H;
    if (H >= max){
      max = H;
      count++;
    }
  }
  
  cout << count;
}

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

using namespace std;

/*helpfull*/
using vl  = vector<long long>;
using vpl = vector<pair<long long, long long>>;
using vs = vector<string>;
using pl  = pair<long long, long long>;
using ll  = long long int;
using vb  = vector<bool>;


struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1> {}(p.first);
        auto hash2 = hash<T2> {}(p.second);
        return hash1 ^ hash2;
    }
};
// #ifndef ONLINE_JUDGE
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
// #endif

// shortcut macros
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mp              make_pair
#define fi              first
#define se              second
// #define mt              make_tuple
#define pb              push_back
#define all(x)          (x).begin(), (x).end()
#define ini(a, v)       memset(a, v, sizeof(a))
#define rep(i, a, n)    for(ll i=a ; i<n ; ++i)
#define For(i, n)       rep(i, 0, n)
#define sz(x)           (int((x).size()))
#define ump(x,y)        unordered_map<x,y>
#define umpr(x,y,z)     unordered_map<x,y,z>
void printcase(ll &x) {
    cout << "Case #" << x << ": ";
}
void read(vector<ll>&v, ll &n) {
    For(i, n)
    cin >> v[i];
}
void read(ll &x) {
    cin >> x;
}
void read(string &s) {
    cin >> s;
}
void read(int &x) {
    cin >> x;
}
void read(ll a[], ll &n) {
    For(i, n)
    cin >> a[i];
}
void print() {
    cout << endl;
}
void write(vector<ll>&v, ll &n) {
    For(i, n)
    cout << v[i] << " ";
    cout << endl;
}
void write(vector<ll>&v) {
    ll n = v.size();
    For(i, n)
    cout << v[i] << " ";
    cout << endl;
}
void write(ll x) {
    cout << x << endl;
}
void write(string &s) {
    cout << s << endl;
}
void write(int &x) {
    cout << x << endl;
}
void write(ll a[], ll &n) {
    For(i, n)
    cout << a[i] << " ";
    cout << endl;
}
const ll mod = 1e9 + 7;





int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    IOS;
    string s1, s2;
    cin >> s1 >> s2;
    ll n1 = sz(s1), n2 = sz(s2);
    vector<vector<ll>> dp(n1 + 1, vl(n2 + 1, 0));
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            }
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    ll i = n1, j = n2;
    string res;
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            res.push_back(s1[i - 1]);
            --i;
            --j;
        }
        else if (dp[i - 1][j] > dp[i][j - 1])
            --i;
        else
            --j;
    }

    // For(i, n1 + 1)
    // write(dp[i]);
    reverse(all(res));
    write(res);

    return 0;
}




Measured memory_bytes: 73660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()

int N;
vector<double> p;

int main() {
  cin >> N;
  p.resize(N);
  rep(i, N) cin >> p[i];

  vector<vector<double>> dp(2, vector<double>(N + 1, 0.0));
  dp[0][0] = 1.0;

  rep(i, N) rep(j, N + 1) {
    int curr = i % 2;
    int next = (i + 1) % 2;

    dp[next][j] = (1.0 - p[i]) * dp[curr][j];
    if (j > 0) dp[next][j] += p[i] * dp[curr][j - 1];
  }

  double ans = 0.0;

  for (int i = (N + 1) / 2; i <= N; ++i) ans += dp[N % 2][i];

  cout << setprecision(10) << ans << endl;

  return 0;
}


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

#define LL long long
#define VI vector<int>
#define VB vector<bool>
#define VL vector<long long>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14

const std::string YES = "YES";
const std::string Yes = "Yes";
const std::string NO = "NO";
const std::string No = "No";

bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }

// 4近傍（右, 下, 左, 上）
const std::vector<int> dy = { 0, -1, 0, 1 };
const std::vector<int> dx = { 1, 0, -1, 0 };

using namespace std;


// 原点からの距離
int dist(int y, int x, int H, int W) {
    if (y == 0) { return x; }
    if (x == W) { return W + y; }
    if (y == H) { return W + H + (W - x); }
    return W + H + W + (H - y);
}

bool on_line(int y, int x, int R, int C) {
    return (x == 0 or x == R) or (y == 0 or y == C);
}

bool solve(int R, int C, int N, vector<tuple<int, int, int, int>> &v) {

    vector<pair<int, int>> line;
    FOR(i, 0, N) {
        int x1, y1, x2, y2;
        tie(x1, y1, x2, y2) = v[i];

        if (on_line(y1, x1, R, C) and on_line(y2, x2, R, C)) {
            line.emplace_back(make_pair(dist(y1, x1, C, R), i));
            line.emplace_back(make_pair(dist(y2, x2, C, R), i));
        }
    }
    sort(ALL(line));

    stack<int> s;
    for (auto p : line) {
        if (!s.empty()) {
            if (s.top() == p.second) {
                s.pop();
            }
            else {
                s.push(p.second);
            }
        }
        else {
            s.push(p.second);
        }
    }

    return s.empty();
}

int main() {
    int R, C, N;
    cin >> R >> C >> N;

    vector<tuple<int, int, int, int>> v;
    FOR(i, 0, N) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        v.emplace_back(make_tuple(x1, y1, x2, y2));
    }

    cout << (solve(R, C, N, v) ? YES : NO) << endl;

    return 0;
}

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

#define REP(i, m, n) for (long long i = (m); i < (long long)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, x) for (long long i = ((long long)(x)-1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
typedef long long ll;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}

ll modpow(ll a, ll p)
{
    if (p == 0)
        return 1;
    if (!(p % 2))
    {
        ll halfP = p / 2;
        ll half = modpow(a, halfP);
        return half * half % mod;
    }
    else
    {
        return a * modpow(a, p - 1) % mod;
    }
}

ll comb(long long a, long long b)
{
    if (b > a - b)
        return comb(a, a - b);
    ll ansMul = 1;
    ll ansDiv = 1;
    for (long long i = 0; i < b; i++)
    {
        ansMul *= a - i;
        ansDiv *= i + 1;
        ansMul %= mod;
        ansDiv %= mod;
    }
    ll ans = ansMul * modpow(ansDiv, mod - 2) % mod;
    return ans;
}

/*
long long num = 200010;
vector<ll> fact(num), ifact(num);
fact[0] = 1;
fact[1] = 1;
for (long long i = 2; i < num; i++) {
    fact[i] = fact[i-1] * i;
    fact[i] %= mod;
}
for (long long i = 0; i < num; i++) {
    ifact[i] = modpow(ifact[i], mod-2);
    ifact[i] %= mod;
}
*/

int main() {
    long long N, T; cin >> N >> T;
    vector<long long> A(N), nums;
    rep(i, N) cin >> A[i];
    long long l = A[0];
    long long r = A[0];
    rep(i, N) {
        if (l < A[i]) {
            r = max(r,A[i]);
        } else if (l >= A[i]) {
            nums.pb(r - l);
            r = A[i];
            l = A[i];
        }
        if (i == N - 1) {
            if (r - l > 0) {
                nums.pb(r - l);
            }
        }
    }
    sort(rall(nums));
    long long x = nums[0];
    long long cnt = 0;
    while (x == nums[cnt]) cnt++;

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

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

int main() {
  int N, N1, N2, N3, N4;
  
  cin >> N;
  
  N1 = N/1000;
  N2 = N/100-N1*10;
  N3 = N/10-N1*100-N2*10;
  N4 = N-N1*1000-N2*100-N3*10;
  
  if ((N1==N2 && N2==N3) || (N2==N3 && N3==N4)) {
  	cout << "Yes" << endl;
  }
  else {
  	cout << "No" << endl;
  }
 }


Measured memory_bytes: 256
x = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
a = int(input())
print(x[a-1])

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

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end

typedef pair<ll,ll> P;
int n; vector<ll> seg; vector<P> laz;
void init(int _n){
   n=1; while(n<_n)n<<=1;
   seg.assign(n*2,0); laz.assign(n*2,P(1,0));
}
void eval(int k,ll lb){
   if(k<n){
      if(laz[k].first){
         laz[k*2].second+=laz[k].second;
         laz[k*2+1].second+=laz[k].second;
      }
      else{
         laz[k*2]=laz[k]; laz[k*2+1]=laz[k];
      }
   }
   if(laz[k].first)seg[k]+=laz[k].second;
   else seg[k]=lb+laz[k].second;
   laz[k]=P(1,0);
}
void update(int a,int b,int x,int k=1,int lb=0,int rb=-1){
   if(rb==-1)rb=n;
   eval(k,lb);
   if(rb<=a or b<=lb)return;
   else if(a<=lb and rb<=b){
      laz[k]=P(0,x); eval(k,lb);
   }
   else{
      int m=(lb+rb)>>1;
      update(a,b,x,k*2,lb,m);
      update(a,b,x,k*2+1,m,rb);
      seg[k]=min(seg[k*2],seg[k*2+1]);
   }
}
ll query(int a,int b,int k=1,int lb=0,int rb=-1){
   if(rb==-1)rb=n;
   eval(k,lb);
   if(rb<=a or b<=lb)return inf;
   else if(a<=lb and rb<=b)return seg[k];
   else return min(query(a,b,k*2,lb,(lb+rb)>>1),query(a,b,k*2+1,(lb+rb)>>1,rb));
}

int main(){
   int n,q; cin>>q>>n;
   init(n);
   rep(i,0,q){
      int lb,rb; cin>>lb>>rb; lb--;
      if(lb==0)update(0,rb,inf);
      else{
         ll val=query(lb-1,lb)-(lb-1);
         update(lb,rb,val);
      }
      ll res=query(0,n)+(i+1);
      if(res>=inf)puts("-1");
      else cout<<res<<endl;
   }
   return 0;
}

Measured memory_bytes: 15640
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N,M;
ll a[10];
const ll matchNum[10]={0,2,5,5,4,5,6,3,7,6};
string dp[10010];
bool valid[100010]={};
int main(){
    cin>>N>>M;
    for(ll i=0;i<M;i++){
      cin>>a[i];
    }
    valid[0]=true;
    for(ll i=0;i<N;i++){
      if(!valid[i])continue;
      for(ll j=0;j<M;j++){
        ll plusMatchNum=matchNum[a[j]];
        ll nextI=i+plusMatchNum;
        if(nextI > N )continue;
        string tmp;
        tmp+=a[j]+'0';
        tmp+=dp[i];
        if( (dp[nextI].length() < tmp.length()) || 
            (dp[nextI].length()== tmp.length() && dp[nextI]<tmp)){
            dp[nextI]=tmp;
            valid[nextI]=true;
        }
      }
    }
    cout<<dp[N]<<endl;
    return 0;
}

Measured memory_bytes: 32384
import java.util.Scanner;

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

		Scanner scan = new Scanner(System.in);
		
		int count = scan.nextInt();
		int blackIndex = scan.nextInt();
		
		int[] answer = new int[count * 2 - 1];
		for (int i = 0; i < answer.length; i++) {
			answer[i] = blackIndex - count + (i + 1);
		}
		
		
		for (int i : answer) {
			System.out.print(i + " ");
		}
	}
}

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

using namespace std;

int main(){
	int n, k;
	cin>>n>>k;
	vector<long long> dp(k,-1);
	dp[0]=0;
	vector<long long> heights(n, 0);
	for(int i=0; i<n; i++)
		cin>>heights[i];
	for(int i=1; i<n; i++){
		long long temp=-1;
		int kn=i-k;
		//cout<<"\ni:"<<i<<"- kn:"<<kn<<"----------";
		//cout<<"\n-------";
		for(int j=0; j<k; j++){
			if(kn+j>=0){
		//		cout<<(kn+j)%k<<","<<kn+j<<"-"<<dp[(kn+j)%k]<<"  ---  ";
				if(temp==-1)
					temp=abs(heights[i]-heights[kn+j])+dp[(kn+j)%k];
				else
					temp=min(temp, abs(heights[i]-heights[kn+j])+dp[(kn+j)%k]);
			}
		}
		//cout<<"\n";
		//cout<<i%k<<" -- "<<temp<<"\n";
		dp[i%k]=temp;
	}
	cout<<dp[(n-1)%k]<<"\n";
}


Measured memory_bytes: 1024
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#define ll long long int
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define PI 3.141592653589793
using namespace std;

int main() {
    ll A,B,K;

    cin >> A >> B >> K;
    if(K <= A) cout << A - K << " " << B << endl;
    else if(K <= A + B) cout << '0' << " " << A + B - K << endl;
    else cout << '0' << " " << '0' << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int main() {
  int h,w;
  cin >> h >> w;
  char c[1005][1005]={};
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++) {
      cin >> c[i][j];
    }
  }
  int dp[1005][1005]={};
  dp[0][0]=1;
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++) {
      if(c[i][j]=='#') {
        continue;
      }
      if(i-1>=0) {
        dp[i][j]+=dp[i-1][j];
      }
      if(j-1>=0) {
        dp[i][j]+=dp[i][j-1];
      }
      dp[i][j]%=MOD;
    }
  }
  cout << dp[h-1][w-1] << endl;
}

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

int main() {
    string S;
    cin >> S;
    bool ok = S[0] == 'A';
    ll C = 0;
    bool small = true;
    for (ll i = 2; i < S.size() - 1; i++) {
        if (S[i] == 'C') {
            C++;
        } else if ('A' <= S[i] && S[i] <= 'Z') {
            small = false;
        }
    }
    if ('A' <= S[1] && S[1] <= 'Z') {
        small = false;
    }
    if ('A' <= S[S.size() - 1] && S[S.size() - 1] <= 'Z') {
        small = false;
    }

    cout << (ok && C == 1 && small ? "AC" : "WA") << endl;
}

Measured memory_bytes: 256
object Main extends App{
  import scala.io.StdIn.readLong
  
  val h = readLong
  
  def attack(x:Long):BigInt ={
    def attackRe(acc:BigInt,amount:BigInt,x:Long):BigInt =
    x match{
      case 1 => acc + amount
      case _ => attackRe(acc + amount ,2*amount ,x/2)
    }
    attackRe(0,1,x)
  }
  
  println(attack(h).toString)
}


Measured memory_bytes: 54556
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N = 1e5 + 5;

int get(int x)
{
	int cnt = 0;
	while(x > 0)
	{
		cnt++;
		x /= 10;
	}
	return cnt;
}

int32_t main()
{
	IOS;
	int n;
	cin >> n;
	int ans = 1e9;
	for(int i = 1; i * i <= n; i++)
	{
		if(n % i == 0)
		{
			ans = min(ans, max(get(i), get(n / i)));
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3600
num=0
k=0
while True:
    n,x=map(int,input().split())
    d = x-n
    if (n,x)==(0,0):
        break
    num=0
    if 3*(n-1)>=x:
        for i in range(3,n+1):
            for j in range(2,i):
                k=x-(i+j)
                if 0<k<j:
                    num+=1
    print(num)


Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N,tmp=0,max=0;
	cin >> N;
	vector <string> A(N);
	map<string,int> B;
	for (size_t i = 0; i < N; i++)
	{
		cin >> A.at(i);
		B[A.at(i)]++;
	}	
	sort(A.begin(), A.end());
	for (size_t i = 0; i < A.size(); i++)
	{
		if (B.at(A.at(i)) > max)max = B.at(A.at(i));
	}
	for (size_t i = 0; i < N; i++)
	{
		if (B.at(A.at(i)) == max) {
			B[(A.at(i))] = 0;
			cout << A.at(i)<<endl;
		}
	}
}

Measured memory_bytes: 28288
from collections import deque

N, M = map(int, input().split())
Node = [[] for _ in range(N + 1)]

for i in range(M):
    a, b = map(int, input().split())
    Node[a].append(b)
    Node[b].append(a)
#print(Node)

seek = [False]*(N+1)
que = deque()
R = []


for n in range(1, N + 1):
    if seek[n] == True:
        #print('already found: {}'.format(n))
        continue
    result = []
    que.append(n)
    result.append(n)
    seek[n] = True
    while len(que) > 0:
        start = que.pop()
        for node in Node[start]:
            if seek[node] == False:
                result.append(node)
                que.append(node)
                seek[node] = True
    R.append(result)

Max = 0
for l in R:
    if len(l) > Max:
        Max = len(l)
print(Max)

Measured memory_bytes: 52044
if __name__ == '__main__':
    N = input()
    array = list(map(int, input().split()))

    old_color = array[0]
    count = 0

    for num in range(1, len(array)):
        color = array[num]
        if old_color == color:
            count += 1
            array[num] = -1
        old_color = array[num]
    print(count)

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
#define rep(i,n) for(int i=0; i<(n);i++)
typedef long long ll;

int main(){
    int n; cin >> n;
    string s; cin >> s;
    int westCount=0;
    int eastCount=0;
    rep(i,n){
        if(s[i]=='E'){
            eastCount++;
        }else{
            westCount++;
        }
    }
    int change_min = 4000000;
    int changeWest=0;
    int changeEast=eastCount;
    rep(i,n){
        if(s[i]=='E'){
            changeEast--;
        }
        if(changeEast + changeWest <= change_min){
            change_min = changeEast + changeWest;
        }
        if(s[i]=='W'){
            changeWest++;
        }
    }
    cout << change_min << endl;
    return 0;
}


Measured memory_bytes: 832
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define mod 1000000007
#define MOD 998244353
#define INF 40000000000000000
int dx8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy8[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};
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 N;
vector<int> Graph[200010];
vector<int> a(200010);
int ans[200010];
vector<int> dp(200010, INF);
int solve(int x) {
    int l = -1, r = 200009;
    while(r - l > 1) {
        int mid = (r + l) / 2;
        if(dp[mid] >= x)
            r = mid;
        else
            l = mid;
    }
    return r;
}
void dfs(int now, int pval = -1) {
    int x = solve(a[now]);
    //cout<<now<<' '<<x<<endl;
    
    int r = dp[x];
    dp[x] = a[now];
    ans[now] = solve(INF - 1);
    for(auto next : Graph[now]) {
        if(next == pval) continue;
        dfs(next, now);
    }
    dp[x] = r;
}
signed main() {
    cin >> N;
    rep(i, N) cin >> a[i];
    rep(i, N - 1) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        Graph[u].push_back(v);
        Graph[v].push_back(u);
    }
    dfs(0);
    rep(i, N) cout << ans[i] << endl;
}


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

int main() {
    int n;
    cin >> n;
    
    bool cards[4][14];
    
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 14; j++) {
            cards[i][j] = 0;
        }
    }
    
    char m;
    int x;
    
    for (int i = 0; i < n; i++) {
        cin >> m >> x;
        if(m == 'S') {
            cards[0][x] = 1;
        }
        else if(m == 'H') {
            cards[1][x] = 1;
        }
        else if(m == 'C') {
            cards[2][x] = 1;
        }
        else if(m == 'D') {
            cards[3][x] = 1;
        }
    }
    
    for(int i = 0; i < 4; i++) {
        for (int j = 1; j < 14; j++) {
            if(cards[i][j] == 1) {
                continue;
            }
            
            if(i == 0) {
                cout << "S " << j << endl;
            }
            else if(i == 1) {
                cout << "H " << j << endl;
            }
            else if(i == 2) {
                cout << "C " << j << endl;
            }
            else if(i == 3) {
                cout << "D " << j << endl;
            }
        }
    }
    
    return 0;
}



Measured memory_bytes: 3092
#include<algorithm>
#include<cmath>
#include<cctype>
#include<iomanip>
#include<iostream>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define out(x) cout << x << endl;
#define each(e, v) for (auto&& e : v)
#define clamp(v,lo,hi) min(max(v,lo),hi)
#define debug(i) cout<<"point :"<< i << endl;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<int> vint;
typedef vector<long> vl;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef map<string, int> mapstri;
typedef map<int, int> mapii;
typedef std::pair<int, int> pairii;

int main () {
    long n,k;
    cin >> n >> k;
    long ans = 0;
    long t = n % k;
    long a = k - t;
    ans = min(a,t);
    out (ans)
    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<double> x(N);
  vector<double> y(N);
  for (int i = 0; i < N; i++){
    cin >> x.at(i) >> y.at(i);
  }
  double sum = 0;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      sum += sqrt((x.at(i)-x.at(j))*(x.at(i)-x.at(j))+(y.at(i)-y.at(j))*(y.at(i)-y.at(j)));
    }
  }
  double n = N;
  double ans = sum / n;
  cout << fixed << setprecision(10);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    inf = float('inf')
    dp = [inf] * n
    dp[0] = 0
    #dp = [0] * n

    for i1 in range(1, n):
        start = max(0, i1 - k)
        #dp[i1] = dp[start] + abs(h[start] - h[i1])
        for i2 in range(start, i1):
            dp[i1] = min(dp[i1], dp[i2] + abs(h[i1] - h[i2]))
    print(dp[n - 1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 57952
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
		String x = "";
		try {
			while ((x = in.readLine()).equals("-1 -1 -1") == false) {
				String[] points = x.split(" ");
				int m = Integer.parseInt(points[0]);
				int f = Integer.parseInt(points[1]);
				int r = Integer.parseInt(points[2]);

				if ((m == -1) || (f == -1)) {
					System.out.println("F");
				} else {
						if ((m + f) >= 80) System.out.println("A");
					if ((m + f) >= 65 && (m + f) < 80) System.out.println("B");
					if ((m + f) >= 50 && (m + f) < 65) System.out.println("C");
					if ((m + f) >= 30 && (m + f) < 50) {
						if (r >= 50) System.out.println("C");
						else System.out.println("D");
					}
					if ((m + f) < 30) System.out.println("F");
				}
			}
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  int sum = 0;
  for(int i=0;i<N;i++){
    cin >> a[i];
    sum += a[i];
  }
  
  int mini = sum;
  int p_sum = 0;
  for(int i=0;i<N;i++){
    p_sum += a[i];
    mini = min(mini,abs(p_sum -(sum -p_sum)));
  }
  
  cout << mini << endl;
}



Measured memory_bytes: 256
#include <iostream>

const int WIDTH = 10;
const int HEIGHT = 3;
const int MAX_BUILDING_NUMBER = 4;
const int SHARP_WIDTH = 20;

void OutputSharp();
void OutputBuilding(const int[HEIGHT][WIDTH]); 
void TenantAndLeaver(int[HEIGHT][WIDTH]);

int main(){
	int NumberOfInformation;  //入力される情報の数
	int BuildingNumber;  //棟番号
	int Floor;  //何階か
	int Th;  //何番目の部屋か
	int NumberOfPeaple;  //入居者人数を出力

	int Building[MAX_BUILDING_NUMBER][HEIGHT][WIDTH] = {};  //入居者をすべて0で初期化

	std::cin >> NumberOfInformation;
	for (int i = 0; i < NumberOfInformation; i++)
	{
		std::cin >> BuildingNumber >> Floor >> Th >> NumberOfPeaple;
		Building[BuildingNumber-1][Floor-1][Th-1] += NumberOfPeaple;
	}

	for (int i = 0; i < MAX_BUILDING_NUMBER; i++){
		OutputBuilding(Building[i]);  //i棟の入居者人数を出力
		if (i != MAX_BUILDING_NUMBER - 1){
			OutputSharp();
		}
	}
}

void OutputSharp(){
	for (int i = 0; i < SHARP_WIDTH; i++){
		std::cout << '#';
	}
	std::cout << std::endl;
}

void OutputBuilding(const int Building[HEIGHT][WIDTH]){
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			std::cout << " " << Building[i][j];
		}
		std::cout << std::endl;
	}
}


Measured memory_bytes: 3080
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	int a,b,c,ans=INF;
	cin>>a>>b>>c;
	ans = min(ans,a+b);
	ans = min(ans,b+c);
	ans = min(ans,c+a);
	cout<<ans<<endl;
}

Measured memory_bytes: 256
// agrawal117
//chahatagrawal117
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long int ll;
ll arr[200005];
ll pre[200005];
int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
     
       
   string a,b;
   cin>>a>>b;
   ll cnt=0;
   for(int i=0;i<a.size();i++){
       if(a[i]==b[i]) cnt++;
   }
   cout<<cnt<<endl;
   
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

int a, b;

int main() {
    cin >> a >> b;
    if (b < 10) {
        b += a * 10;
    } else if (b < 100) {
        b += a * 100;
    } else {
        b += a * 1000;
    }

    int sq = sqrt(b);

    if (b == sq * sq) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


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

#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<ll,ll>
#define vi vector<int>
#define vpi vector< pi > 
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL)
const int N=202;
int a[N][N];
int gcd(int x,int y)
{
	if(y==0) return x;
	return gcd(y,x%y);
}
int main()
{
	for(int i=1;i<N;i++)
	{
		for(int j=1;j<N;j++)
			a[i][j]=gcd(i,j);
	}
	int n;
	cin>>n;
	ll res=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				int g=a[i][j];
				res+=a[g][k];
			}
		}
	}
	cout<<res;
	return 0;
}

Measured memory_bytes: 3792
#include <iostream>
#include <stdlib.h>
#define N 99999
using namespace std;
 
typedef struct p{
    char name[10];
    int time;
};
 
int main(){
 
    int i;
    int n;
    int q;
    int head;
    int tail;
    int res_time = 0;
    char temp[10];
    p A[N];
 
    cin >> n;
    cin >> q;
 
    for (i = 0; i < n; i++){
        cin >> A[i].name;
        cin >> A[i].time;
    }
 
    head = 0;
    tail = n - 1;
 
    while (1){
        A[head].time -= q;
        if (A[head].time <= 0){
            res_time += q + A[head].time;
            cout << A[head].name << ' ' << res_time << endl;
            if (tail == head){
                break;
            }
        }
        else {
            tail++;
            if (tail == N){
                tail = 0;
            }
            A[tail] = A[head];
            res_time += q;
        }
        head++;
        if (head == N){
            head = 0;
        }
    }
 
    return 0;
}


Measured memory_bytes: 4524
n = gets.to_i
a = gets.chomp.split.map(&:to_i)
res = 0
hs = Hash.new(0)
a.each do |x|
  hs[x] += 1
  res += x
end

q = gets.to_i
q.times do
  b, c = gets.chomp.split.map(&:to_i)
  res -= b * hs[b]
  res += c * hs[b]
  puts res
  hs[c] += hs[b]
  hs[b] -= hs[b]
end

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

using namespace std;

inline int ctoi(char c) { if(c < '0' || '9' < c) throw invalid_argument("ctoi error"); return c - '0'; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
inline T gcd(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("gcd error: x <= 0 or y <= 0");
	
	if(x < y) swap(x, y);
	T r = x % y;

	while(r != 0){
		x = y;
		y = r;
		r = x % y;
	}

	return y;
}
template <typename T>
inline T lcm(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("lcm error: x <= 0 or y <= 0");

	return x * y / gcd(x, y);
}

bool comp(pair<int, int> a, pair<int, int> b){
	if(a.second != b.second){
		return a.second > b.second;
	}
	else{
		return a.first < a.first;
	}
}

int main(){
	int n;
	cin >> n;
	int left[100000 + 1] = {};
	int right[100000 + 1] = {};
	
	//バケツ
	rep(i, n){
		int a;
		cin >> a;

		if(i % 2 == 0){
			left[a]++;
		}
		else{
			right[a]++;
		}
	}

	//バケツからvectorに変換
	vector<pair<int, int>> vleft;
	vector<pair<int, int>> vright;

	rep(i, 100000 + 1){
		if(left[i] != 0){
			pair<int, int> p = make_pair(i, left[i]);
			vleft.push_back(p);
		}

		if(right[i] != 0){
			pair<int, int> p = make_pair(i, right[i]);
			vright.push_back(p);
		}
	}

	//pairのsecondでソート
	sort(all(vleft), comp);
	sort(all(vright), comp);

	//leftとrightで、それぞれそろえるべき数を決定する
	if(vleft.front().first == vright.front().first){
		if(vleft.size() == 1 && vright.size() == 1){
			cout << vleft.front().second << "\n";
			return 0;
		}

		if(vleft.front().second == vright.front().second){
			if(vleft[1].second >= vright[1].second){
				cout << n/2-vleft[1].second + n/2-vright.front().second << "\n";
			}
			else{
				cout << n/2-vleft.front().second + n/2-vright[1].second << "\n";
			}
		}
		else{
			if(vleft.front().second >= vright.front().second){
				cout << n/2-vleft.front().second + n/2-vright[1].second << "\n";
			}
			else{
				cout << n/2-vleft[1].second + n/2-vright.front().second << "\n";
			}
		}
	}
	else{
		cout << n/2-vleft.front().second + n/2-vright.front().second << "\n";
	}

	/*
	cout << "left:" << "\n";
	for(auto i : vleft) cout << i.first << " " << i.second << "\n";
	cout << "right" << "\n";
	for(auto i : vright) cout << i.first << " " << i.second << "\n";
	*/

	return 0;
}

Measured memory_bytes: 2044
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long n,k;
    scanf("%ld %ld", &n, &k);
    vector<pair<int, int>> viiSegment(k);
    for(long i = 0; i < k; i++){
        int l,r;
        scanf("%d %d", &l, &r);
        viiSegment[i] = make_pair(l,r);
    }
    
    vector<int> viCount(n+1, 0);
    for(long i = 0; i < k; i++){
        for(int j = viiSegment[i].first; j <= viiSegment[i].second; j++){
            viCount[j] = 1;
        }
    }
    
    vector<long> viDP(n+1,0);
    vector<long> viDPSum(n+1, 0); //累積和
    for(int i = 1; i < n+1; i++){
        viDP[i] = viCount[i];
        for(long j = 0; j < k; j++){
            int iLeft = max((i - viiSegment[j].second - 1), 0);
            int iRight = max((i - viiSegment[j].first), 0);
            viDP[i] += (viDPSum[iRight] - viDPSum[iLeft]);
            viDP[i] %= 998244353;
        }
        viDPSum[i] = viDPSum[i-1] + viDP[i];
    }
    
    printf("%ld", viDP[n-1]);
    return 0;
}


Measured memory_bytes: 6760
let readIntArray _ =
    stdin.ReadLine().Split(" ") |> Array.map int64

let rec solve time sum list =
    match list with
    | [] -> sum
    | [ _ ] -> sum + time
    | x :: y :: xx -> if x + time <= y then solve time (sum + time) (y :: xx) else solve time (sum + y - x) (y :: xx)

()
|> readIntArray
|> fun [| _; t |] ->
    ()
    |> readIntArray
    |> Array.toList
    |> solve t 0L
    |> printfn "%d"


Measured memory_bytes: 60968
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }

    if (N == K) {
      System.out.println(1);
      return;
    }
    if (K == 2) {
      System.out.println(N-1);
      return;
    }
    if (N % (K-1) > 1) {
      System.out.println(N / (K-1) + 1);
    } else {
      System.out.println(N / (K-1));
    }
  }
}

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

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define INF 1000000007LL

#define cil(a,b) ( ((a)%(b) == 0)?((a)/(b)):((a)/(b)+1) )

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef vector<pii> vii;

ll mypow(ll a, ll b) { if(b == 0) return 1; ll temp=mypow(a,b/2); temp=(temp*temp)%INF; if(b%2 == 1) temp=(a*temp)%INF; return temp; }
int mygcd(int a, int b) { if(b==0) return a; return mygcd(b,a%b); }
int cntBits(ll a) { int ret=0; while(a>0) { ret++; a/=2; } return ret; }
ll arr[100010];
int main()
{
	ios::sync_with_stdio(0);
	int tt=1; 
//	cin >> tt;
	for(int tcase=1;tcase<=tt;tcase++)
	{
		int n; cin >> n;
		for(int i=0;i<n;i++) cin >> arr[i];
		sort(arr,arr+n);
		list<ll> v; v.clear();
		v.push_front(arr[0]);
		int l=1,r=n-1;
		while(l<=r)
		{
			ll val1=abs(arr[r]-v.front()), val2=abs(arr[r]-v.back()), val3=abs(arr[l]-v.front()), val4=abs(arr[l]-v.back());
			ll val5=max(val1,max(val2,max(val3,val4)));
			if(val5==val1) { v.push_front(arr[r]); r--; }
			else if(val5==val2) { v.push_back(arr[r]); r--; }
			else if(val5==val3) { v.push_front(arr[l]); l++; }
			else { v.push_back(arr[l]); l++; }
		}
		ll ans=0,prev=v.front(); v.pop_front();
		while(!v.empty())
		{
			ans+=abs(v.front()-prev);
			prev=v.front();
			v.pop_front();
		}
		cout << ans << "\n";
	}
	return 0;
}


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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


int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    
    string S;
    cin >> S;

    int ans = 0;
    for(int i = 0; i < 4; i++){
        if(S[i] == '+'){
            ans++;
        }else{
            ans--;
        }
    }

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


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

int main()
{
    string S;
    cin >> S;
    
    int flag = 0;
    bool ans = false;
    if(S.at(0) == 'A'){
        S.at(0) = 'a';
        for(int i=2; i<(int)S.size()-1; i++){
            if(S.at(i) == 'C'){
                S.at(i) = 'c';
                flag += 1;
            }
        }
        if(flag == 1){
            for(int j=0; j<(int)S.size(); j++){
                    if(islower(S.at(j))){
                        ans = true;
                    }else{
                        ans = false;
                        break;
                    }
            }
        }
    }
    if(ans == true){
        cout << "AC" << endl;
    }else{
        cout << "WA" << endl;
    }   
}



Measured memory_bytes: 3600
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[][] ary = new int[n][2];
        for (int i = 0; i < n; i++) {
            ary[i][0] = Integer.parseInt(sc.next());
            ary[i][1] = Integer.parseInt(sc.next());
        }
        double sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                sum += Math.sqrt(Math.pow(ary[i][0] - ary[j][0], 2) + Math.pow(ary[i][1] - ary[j][1], 2));
            }
        }
        System.out.println(2 * sum / n);
    }
}

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

using namespace std;

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

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

    ll x,y;cin>>x>>y;
    if(x>=y) cout<<gcd(x,y)<<endl;
    else cout<<gcd(y,x)<<endl;
}

Measured memory_bytes: 3204
#include <iostream>
using namespace std;
int main (void) {
    int A;
    int B;
    int X;

    cin >> A >> B >> X;

    if (A > X) {
        cout << "NO" << endl;
    } else if (A + B >= X) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n = INT()
    ans = 0

    lis = [[0]*9 for _ in range(9)]

    for i in range(1, n+1):
        s = str(i)
        a, b = s[0], s[-1]
        if "0" in [a, b]: continue
        lis[int(a)-1][int(b)-1] += 1


    for i in range(9):
        for j in range(9):
            ans += lis[i][j] * lis[j][i]

    print(ans)



if __name__=='__main__':
    main()


Measured memory_bytes: 5144
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
const int N=3e5+100,mod=998244353;
int n,m,ans,f[N][3],pw[N],sg[N];
vector<int> G[N];
int main() {
	scanf("%d",&n);
	pw[0]=1, pw[1]=(LL)(1e18)%mod;
	for(int i=2;i<=n;++i)
		pw[i]=(LL)pw[i-1]*pw[1]%mod;
	for(int o=0;o<3;++o) {
		scanf("%d",&m);
		for(int i=1;i<=n;++i) sg[i]=0, G[i].clear();
		for(int i=1,x,y;i<=m;++i) {
			scanf("%d%d",&x,&y);
			if(x>y) swap(x,y);
			G[x].pb(y);
		}
		for(int u=n;u>=1;--u) {
			set<int> mex;
			for(auto v:G[u]) {
				mex.insert(sg[v]);
				while(mex.count(sg[u]))
					++sg[u];
			}
			(f[sg[u]][o] += pw[u])%=mod;
		}
	}
	for(int i=0;i<=500;++i)
		for(int j=0;j<=500;++j)
			(ans += (LL)f[i][0]*f[j][1]%mod*f[i^j][2]%mod)%=mod;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 14160
#include<stdio.h>
using namespace std ;
int n,m,x,X[20],S=0,d[20][20],sum=99999999;
void F(int i)
{
    if(i>n)return ;
    int j,flag;
    F(i+1);
    for(j=1;j<=m;j++)
    {
        X[j]+=d[i][j];
    }
    S+=d[i][0];
    for(j=1,flag=1;j<=m;j++)
    if(X[j]<x){flag=0;break;}
    if(flag==1){if(S<sum)sum=S;}
    F(i+1);
    for(j=1;j<=m;j++)
    {
        X[j]-=d[i][j];
    }
    S-=d[i][0];
}
int main()
{
    int i,j;
    scanf("%d%d%d",&n,&m,&x);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&d[i][0]);
        for(j=1;j<=m;j++)scanf("%d",&d[i][j]);
    }
    F(1);
    if(sum==99999999)printf("-1\n");
    else printf("%d\n",sum);
}



Measured memory_bytes: 1708
N, Q = gets.split(' ').map(&:to_i)
s = gets.chomp.split('')
count = [0]

s.length.times do |i|
  count[i + 1] = "#{s[i]}#{s[i + 1]}" == 'AC' ? count[i] + 1 : count[i]
end

Q.times do |i|
  l, r = gets.split(' ').map(&:to_i)
  puts count[r - 1] - count[l - 1]
end

Measured memory_bytes: 11004
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val l = Array(n) { sc.nextInt() }
    var ans = 0
    for (i in 0 until n) {
        for (j in i + 1 until n) {
            for (k in j + 1 until n) {
                if (l[i] != l[j] && l[j] != l[k] && l[k] != l[i] && Math.abs(l[i] - l[j]) < l[k] && l[k] < l[i] + l[j]) {
                    ans++
                }
            }
        }
    }
    println(ans)
}

fun main() {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 36088