akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
typedef __int128_t Int;
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T> void printvv(const vector<vector<T>> &v) {
  cerr << endl;
  rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
    if (typeid(v[i][j]) == typeid(INF) and v[i][j] == INF) {
      cerr << "INF";
    } else
      cerr << v[i][j];
    cerr << (j == v[i].size() - 1 ? '\n' : ' ');
  }
  cerr << endl;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < s.length(); i++)
    if ('0' <= s[i] && s[i] <= '9')
      ret = 10 * ret + s[i] - '0';
  return ret;
}

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

int gcd(int x, int y) { return (y == 0 ? x : gcd(y, x % y)); }
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  int N, M;
  cin >> N >> M;
  int ans = 0;

  for (int i = 1; i * i <= M; i++) {
    if (M % i == 0) {
      int x = M / i;

      if (x >= N)
        chmax(ans, i);
      if (i >= N)
        chmax(ans, x);
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
//knapsack 1 -->akash_codex
#include<iostream>
typedef long long ll;
using namespace std;
ll dp[101][100001];
ll n,w;
ll max_val(ll value[],ll weight[],ll idx,ll capacity){
	if(idx==n || capacity==0) return 0;
	ll max1=0,max2=0;
	
	if(dp[idx][capacity]==-1){
	if(capacity-weight[idx]>=0) max1=value[idx]+max_val(value,weight,idx+1,capacity-weight[idx]);
	max2=max_val(value,weight,idx+1,capacity);
	dp[idx][capacity]=max(max1,max2);
 }
	return dp[idx][capacity];
}
int main(){

	cin>>n>>w;
	ll value[n],weight[n];
	for(ll i=0;i<101;i++)
	for(ll j=0;j<100001;j++) dp[i][j]=-1;
    for(ll i=0;i<n;i++) cin>>weight[i]>>value[i];
	cout<<max_val(value,weight,0,w);
	return 0;
}

Measured memory_bytes: 82496
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def main():
    N = int(readline())
    a = Counter(prime_factorize(N))

    ans = 0
    for power in a.values():
        tmp = power
        for j in range(1, power + 1):
            if tmp >= j:
                tmp -= j
                ans += 1
            else:
                break

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9516
from bisect import bisect

a, b, q = [int(i) for i in input().split()]
s = []
for i in range(a):
	s.append(int(input()))
s = [-float('inf')] + s + [float('inf')]
t = []
for i in range(b):
	t.append(int(input()))
t = [-float('inf')] + t + [float('inf')]
x = []
for i in range(q):
	x.append(int(input()))

for xx in x:
  
  s_i = bisect(s,xx)
  s_r = abs(xx - s[s_i])
  s_l = abs(xx - s[s_i-1])
  t_i = bisect(t,xx)
  t_r = abs(xx - t[t_i])
  t_l = abs(xx - t[t_i-1])

  
  #print(s_l,s_r,t_l,t_r)
  
  #l = max(s_l,t_l)
  #r = max(s_r,t_r)
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    l = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    rl = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
  

Measured memory_bytes: 18192
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vpint> vvpint;
typedef vector<vpll> vvpll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<string>> vvstring;
typedef vector<vector<bool>> vvbool;

typedef vector<vector<vector<ll>>> vvvll;

const int c_YET = -1;
const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const ll MAX = 1e9;
const double PI = 3.14159265358979323846264338327950288;
//========================================================================





int main() {

	////==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	////==================================
	

	vint a(3), b(3);
	for (int i = 0; i < 3; i++)
	{
		cin >> a[i] >> b[i];
		a[i]--;
		b[i]--;
	}


	vint sum(4);
	for (int i = 0; i < 3; i++)
	{
		sum[a[i]] ++;
		sum[b[i]] ++;
	}

	int one = 0;
	int two = 0;
	for (int i = 0; i < 4; i++)
	{
		if (sum[i] == 1)
		{
			one++;
		}
		else if(sum[i] == 2)
		{
			two++;
		}
	}

	if (one == 2 && two == 2)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}

}





Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int M[501][501];
  int n,i,j,U,k,V;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++) M[i][j]=0;
  }
  for(i=0;i<n;i++){
    scanf("%d%d",&U,&k);
    U--;
    for(j=0;j<k;j++){
      scanf("%d",&V);
      V--;
      M[U][V]=1;
    }
  }
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(j)printf(" ");
      printf("%d",M[i][j]);
    }
    printf("\n");
  }
  return 0;
}






Measured memory_bytes: 2060
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e15;

signed main() {
	int N, T;
	cin >> N >> T;
	vector<int>t(N);
	rep(i, N)cin >> t[i];
	int now;
	int sum = 0;
	for (int i = 0; i < N - 1; i++) {
		now = t[i];
		if (now + T < t[i + 1]) {
			sum += T;
			now = t[i + 1];
		}
		else {
			sum += t[i + 1] - now;
			now = t[i + 1];
		}
	}
	cout << sum + T;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    int N, T, c, t;
    cin >> N >> T;
    int res = 1001;
    REP(i, N) {
        cin >> c >> t;
        if (t <= T) {
            amin(res, c);
        }
    }
    if (res == 1001) {
        cout << "TLE" << endl;
    } else {
        cout << res << endl;
    }
    return 0;
}


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

using namespace std;

int N, M, size;
int ans, a[10];
vector<int> ast;

int _2(int x){
  int s = x*2, t = 0;

  while(s > 0){
    t += s % 10;
    s /= 10;
  }
  return t;
}

void solve(int d, int sum){
  if(d == size){
    if(sum % 10 == 0){
      ans++;
    }
    return;
  }

  int _ast = ast[d];
  for(int i = 0 ; i < M ; i++){
    if(_ast == 2){
      int s = _2(a[i]);
      solve(d+1,sum+s);
    }else{
      solve(d+1,sum+a[i]);
    }
  }
}

int main(){
  char ch;
  int sum = 0; ans = 0;

  cin >> N;
  for(int i = 0 ; i < N ; i++){
    cin >> ch;
    if((N-i)%2 == 0){
      if(ch == '*'){
        ast.push_back(2);
      }else{
        sum += _2(ch - '0');
      }
    }else{
      if(ch == '*'){
        ast.push_back(1);
      }else{
        sum += (ch - '0');
      }
    }
  }   

  cin >> M;
  for(int i = 0 ; i < M ; i++){
    cin >> a[i];
  }
  size = ast.size();
  solve(0, sum);
  cout << ans << endl;    
  
  return 0;
}

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

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-12;
static const double PI = acos(-1.0);

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#define DEBUG(x) cout << #x << ": " << x << endl

void solve(long long N, std::vector<long long> A) {
  sort(begin(A), end(A), greater<ll>());
  ll ans = 0;
  FOR(i, 1, N) {
    ans += A[i / 2];
  }
  cout << ans << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }
  solve(N, std::move(A));
  return 0;
}


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

using namespace std;

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        long long int a[105],maxi,mini;
        for(int i = 0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            if(i==0)
                maxi=mini=a[i];
            if(a[i]>maxi)
                maxi=a[i];
            if(a[i]<mini)
                mini=a[i];
        }
        printf("%lld\n",maxi-mini);
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;
ll H, W, A, B;

// Combination
const ll COMB_MAX = 1e6;
ll fac[COMB_MAX], finv[COMB_MAX], inv[COMB_MAX];
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < COMB_MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
ll COM(ll n, ll k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

signed main()
{
    cin >> H >> W >> A >> B;
    ll ans = 0;
    COMinit();

    for (ll x = B; x < W; ++x) {
        ll w1 = x;
        ll h1 = (H - A - 1);
        ll sum1 = COM(w1 + h1, w1);
        ll w2 = W - w1 - 1;
        ll h2 = A - 1;
        ll sum2 = COM(w2 + h2, w2);
        ans += (sum1 * sum2) % MOD;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 23680
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
ll a,b,ans;
ll Xor(ll x){
  ll p=(x+1)>>1,q=p&1;
  if((x&1)==0) q=q^x;
  return q;
}
int main(){
  fast;
  cin>>a>>b;
  ans=Xor(a-1)^Xor(b);
  cout<<ans;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
 
int n, k, l;
map<pi, int> mp;
 
vector<int> gph1[200005], gph2[200005];
int c1[200005], c2[200005];
 
void dfs1(int x, int c){
	if(c1[x]) return;
	c1[x] = c;
	for(auto &i : gph1[x]) dfs1(i, c);
}
 
void dfs2(int x, int c){
	if(c2[x]) return;
	c2[x] = c;
	for(auto &i : gph2[x]) dfs2(i, c);
}
 
int main(){
	cin >> n >> k >> l;
	for(int i=0; i<k; i++){
		int x, y;
		scanf("%d %d",&x,&y);
		gph1[x].push_back(y);
		gph1[y].push_back(x);
	}
	for(int i=0; i<l; i++){
		int x, y;
		scanf("%d %d",&x,&y);
		gph2[x].push_back(y);
		gph2[y].push_back(x);
	}
	int p1 = 0, p2 = 0;
	for(int i=1; i<=n; i++){
		if(!c1[i]) dfs1(i, ++p1);
		if(!c2[i]) dfs2(i, ++p2);
		mp[pi(c1[i], c2[i])]++;
	}
	for(int i=1; i<=n; i++){
		printf("%d ", mp[pi(c1[i], c2[i])]);
	}
}

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

int main(){
    ll t,n,q,m,x,y,aa=0,b=0,c=0,d=0;
    cin>>t;
    ll a[t];
    for(int i=0;i<t;i++)
        cin>>a[i];
    sort(a,a+t);
    c=2;
    d=a[t-1];
    b = t-2;
    while(c<t){
        d += min((ll)2,t-c)*a[b];
        c += min((ll)2,t-c);
        b--;
    }
    cout<<d<<endl;
    return 0;
}







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

int main() {
	std::string S, T;
	std::cin >> S >> T;

	int result = 0;
	for(int i = 0; i < 3; i++) {
		if(S[i] == T[i]) {
			result++;
		}
	}

	std::cout << result << std::endl;

	return 0;
}


Measured memory_bytes: 256
from itertools import accumulate

N = int(input())
A = [int(input()) for _ in range(N)]

inf = float('inf')

L = list(accumulate(A, max))
R = list(accumulate(reversed(A), max))

L = [-inf] + L
R = [-inf] + R[:-1]

M = (max(l, r) for l, r in zip(L, reversed(R)))

for m in M:
    print(m)

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

int main(){
  int N;
  int n, a;
  cin >> N ;
  n = N /1000;
  a = N % 1000;
  if(a == 0) cout << n* 1000 - N << endl;
  else cout << (n + 1)* 1000 - N << endl;
   
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Map = map<string,ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
ll INF=1LL<<60;
ll MOD=1000000007;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N,0);
    for(ll i=0;i<N;i++){
        cin>>A[i]
    ;}
    sort(A.begin(), A.end());
    ll ans=0;
    ll t=A[N/2];
    if(N%2){
        for(ll i=0;i<N;i++){
                ans+=2*llabs(A[i]-t);
        ;}
        ans-=min(llabs(A[N/2+1]-A[N/2]),llabs(A[N/2-1]-A[N/2]));
    }
    else {
        for(ll i=0;i<N;i++){
            if(i!=N/2&&i!=N/2-1){
                ans+=2*llabs(A[i]-t);
            }
        ;}
        ans+=llabs(A[N/2]-A[N/2-1]);
    }
    cout<<ans<<endl;

    
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
const ll INF = 1e10;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
int main(){
    string s,t = "";
    cin >> s;
    int i = 0,l = s.length();
    s += "dreamer";
    while(i < l){
        if (s[i] == 'd'){
            t += "dream";
            i += 5;
            if (s[i] == 'e' && s[i+1] == 'r' && (s[i+2] == 'd' || s[i+2] == 'e')){
                t += "er";
                i += 2;
            }
        }
        else{
            t += "erase";
            i += 5;
            if (s[i] == 'r'){
                t += "r";
                i += 1;
            }
        }
    }
    bool out = 0;
    rep(i,l){
        if (t[i] != s[i]) out = 1;
    }
    if (out || t.length() > l) PRINT("NO");
    else PRINT("YES");
}

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

int n, m;
const int N = 100000;
vector <int> G[N + 7];
long long wynik;
int odw[N + 7];
int kol[N + 7];
int ile;
int dwu;

void dfs(int v) {
	odw[v] = 1;
	ile++;
	for(auto u : G[v]) {
		if(!odw[u]) {
			kol[u] = kol[v] ^ 1;
			dfs(u);
		}
		else if(kol[u] != (kol[v] ^ 1)) dwu = 0;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	wynik = (long long) n * n;
	vector <pair <int, int> > sizes;
	
	for(int i = 1; i <= n; ++i) {
		if(!odw[i]) {
			ile = 0;
			dwu = 1;
			kol[i] = 1;
			dfs(i);
			if(ile > 1) sizes.push_back({ile, dwu});
		}
	}
	
	long long suu = 0;
	for(auto u : sizes) suu += u.first;
	for(auto u : sizes) wynik -= suu * u.first;
	long long siz = sizes.size();
	siz *= siz;
	wynik += siz;
	siz = 0;
	for(auto u : sizes) if(u.second) siz++;
	siz *= siz;
	wynik += siz;
	cout << wynik << endl;	
	return 0;
}	

Measured memory_bytes: 9472
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N, M;
  cin>>N>>M;
  pair<int, int> ans[M];
  int a=1, b=N;
  map<int, int> amap;
  for(int i=0;i<M;++i) {
    ans[i] = mp(a, b);
    amap[b-a]++;
    amap[N-(b-a)]++;
    a++;
    b--;
    while(amap[b-a]>0 || b-a==N-(b-a)) {
      b--;
    }
  }
  for(int i=0;i<M;++i) cout<<ans[i].fi<<" "<<ans[i].se<<endl;
}


Measured memory_bytes: 12484
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n;

        while(true){
            n = Integer.parseInt(br.readLine());
            if(n == 0){
                break;
            }

            String[] str = br.readLine().split(" ");
            double ave = 0;
            double alpha = 0;
            double[] line = new double[n];
            for(int i = 0; i < n; i++){
                line[i] = Double.parseDouble(str[i]);
                ave += line[i];
            }
            ave /= n;

            for(int i = 0; i < n; i++){
                alpha += Math.pow((line[i]-ave), 2);
            }
            alpha /= n;
            sb.append(Math.sqrt(alpha)).append("\n");
        }
        System.out.print(sb.toString());
    }
}

Measured memory_bytes: 26316
#include<bits/stdc++.h>
#define ll long long
#define REP(i, n) for (int i=0; i<n; ++i)
#define print(x) cout << x << endl;

using namespace std;

void solve() {
    int N;
    cin >> N;
    vector<int> X(N), tmp;
    REP(i, N) cin >> X[i];

    tmp = X;
    sort(tmp.begin(), tmp.end());

    int left = tmp[N/2-1];
    int right = tmp[N/2];
    vector<int> ans(N);
    REP(i, N) {
        if (X[i] <= left) {
            ans[i] = right;
        } else {
            ans[i] = left;
        }
    }
    REP(i, N) {
        print(ans[i]);
    }
}

int main() {

    solve();
    return 0;
}


Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
	int n;
	cin>>n;
	vector<int> v;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	cout<<v[v.size()/2]-v[v.size()/2-1]<<endl;
	return 0;
}

Measured memory_bytes: 1148
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define mod ((ll)1e9+7)
#define maxx ((ll)1e6+5)
#define pb push_back
#define ins insert
#define usefile freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define test ll t; cin>>t; while(t--)
ll exp(ll x,ll y,ll p){ ll res=1; while(y) {if(y%2) res=(res*x%p)%p; x=(x*x)%p; y/=2; } return res;}
ll expo(ll x,ll y){ ll res=1; while(y) {if(y%2) res=(res*x%mod)%mod; x=(x*x)%mod; y/=2; } return res;}
/*int sv[1000000]={0};
ll fact[1000007]={0};
void facto() {fact[0]=1;fact[1]=1;for(int i=2;i<100007;i++)fact[i]=(fact[i-1]*i)%mod;}
void sve() {sv[0]=1;sv[1]=1;for(int i=2;i*i<=maxx;i++){if(!sv[i]){for(int j=2*i;j<=maxx;j+=i)sv[j]=1;}}}//0 hai to prime
ll ncr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(expo(fact[r],mod-2)))%mod; res=(res*(expo(fact[n-r],mod-2)))%mod; return res;}
ll npr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(expo(fact[n-r],mod-2)))%mod; return res;}*/
int a[3][100003];
using namespace std;
signed main()
{
    int n,k,i,j;
    cin >> n >> k;
    int a[n],d[n] = {0};
    for(i=0 ; i<n ; i++)
    	cin >> a[i];
    for(i=1 ; i<n ; i++)
    {
    	int p = 1e17;
    	for(j=i-1 ; j>=i-k && j>=0 ; j--)
    		p = min(p, d[j]+abs(a[j]-a[i]));
    	d[i] = p;
    }
    cout << d[n-1] <<"\n";
    return 0;
}

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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const ll INF = 1<<21;
// static const ll MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

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

    int k;
    cin >> k;

    int n;
    n = s.size();

    set<string> st;
    for(int in=0;in<n;in++) {
        for(int jk=1;jk<=k;jk++) {
            st.insert(s.substr(in, jk));
        }
    }

    auto itr = st.begin();
    for(int ik=1;ik<k;ik++) itr++;

    cout << *itr << endl;

    return 0;
}


Measured memory_bytes: 1664
// AOJ 0594
#include<iostream>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

int abs(int x) {
  return (x > 0 ? x : -x);
}

int dist(int x, int y) {
//  cout << "dist(" << x << "," << y << ")";
  if (x * y > 0) {
    x = abs(x), y = abs(y);
    return x + y - min(x, y);
  } else {
    x = abs(x), y = abs(y);
    return x + y;
  }
}

int main() {
  int W, H, N;
  cin >> W >> H >> N;

  int ans = 0;
  int ox, oy;
  cin >> ox >> oy;
  REP(i, N - 1) {
    int nx, ny;
    cin >> nx >> ny;
    int d = dist(nx - ox, ny - oy);
//    cout << "=" << d << endl;
    ans += d;
    ox = nx, oy = ny;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1164
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
			　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <memory>
#include <iomanip>
#include <type_traits>

#define rep(i, n) for(Int (i) = 0; (i) < (n); ++(i))
#define all(n) std::begin(n), std::end(n)
#define debug(var) std::cout << #var << ": " << var << "\n"
using Int = int64_t;
constexpr Int INF = INT_MAX;
constexpr Int mod = 1e9 + 7;


void calc() {

	Int a, b, c; std::cin >> a >> b >> c;
	if (a + b == c || b + c == a || c + a == b)std::cout << "Yes";
	else std::cout << "No";
	
}


int main() {

	calc();

	return 0;
}

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

using pii = pair<int, int>;

struct point {
    int y, x, pls;
    bool operator<(point const& other) const {
        int sl1 = y * other.x;
        int sl2 = other.y * x;
        if(sl1 == sl2) {
            return pls < other.pls;
        }
        return sl1 < sl2;
    }
};

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> v(H);
    vector<point> ps;
    for(int i=0; i<H; ++i) {
        cin >> v[i];
    }
    for(int i=0; i<H; ++i) {
        for(int j=0; j<W; ++j) {
            if(v[i][j] == '#') {
                if((i == H-1 || v[i+1][j] == '.') && (j == W-1 || v[i][j+1] == '.')) {
                    ps.push_back(point{H-i-1, j+1, 1});
                }
                if((i == 0 || v[i-1][j] == '.') && (j == 0 || v[i][j-1] == '.')) {
                    ps.push_back(point{H-i, j, -1});
                }
            } else if(v[i][j] == '.') {
                if((i != H-1 && v[i+1][j] == '#') && (j != W-1 && v[i][j+1] == '#')) {
                    ps.push_back(point{H-i-1, j+1, 1});
                }
                if((i != 0 && v[i-1][j] == '#') && (j != 0 && v[i][j-1] == '#')) {
                    ps.push_back(point{H-i, j, -1});
                }
            }
        }
    }
    sort(ps.begin(), ps.end());
    int now = 1;
    int res = now;
    for(auto& p : ps) {
        now += p.pls;
        res = max(res, now);
    }
    cout << res << endl;
}


Measured memory_bytes: 5236
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#define in(n, m) for (int i=n; i<m;i++)
#define inj(n, m)for (int j=n; j<m;j++)
#define ink(n, m)for (ll k=n; k<m;k++)
using namespace std;
using ll=long long;
using P =pair<ll, ll>;
const ll INF = 1LL << 60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int n, s;
bool can;
int ans;
int x;


int main() {
	string S;
	cin >> S;
	if (S == "ABC") cout << "ARC" << endl;
	else if (S == "ARC") cout << "ABC" << endl;
	return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>

using namespace std;

const double DTR = (2 * acos(-1)) / 360;

double myfmod(double x, double y) { return x - (int) (x / y) * y; }
 
enum ans {
        ABC, ACD, ADB, BCD,
};

int solve() {
        string xy;
        cin >> xy;
        int d, l;
        scanf("%d%d", &d, &l);
        double base = 
                xy == "BC" ? -60 :
                xy == "CD" ? 0 :
                xy == "DB" ? 60:
                0;
        double theta = (base + d) * DTR;
        double y = l * sin(theta);
        double x = l * cos(theta);
        double z60 = x + sqrt(3) / 3.0 * y;
        double z120 = -x + sqrt(3) / 3.0 * y;
        z60 = fmod(fmod(z60, 2.0) + 2.0, 2.0);
        z120 = fmod(fmod(z120, 2.0) + 2.0, 2.0);
        y = (z60 + z120) * sqrt(3) / 2.0;
        if (z60 < 1.0) {
                if (z120 < 1.0) {
                        if (y < sqrt(3) / 2.0) {
                                return ADB;
                        } else {
                                return BCD;
                        }
                } else {
                        if (y < sqrt(3)) {
                                return ABC;
                        } else {
                                return ACD;
                        }
                } 
        } else {
                if (z120 < 1.0) {
                        if (y < sqrt(3)) {
                                return ACD;
                        } else {
                                return ABC;
                        }
                } else {
                        if (y < 3.0 * sqrt(3) / 2.0) {
                                return BCD;
                        } else {
                                return ADB;
                        }
                }
        }
}

int main() {
        int a = solve(), b = solve();
        puts(a == b ? "YES" : "NO");
        return 0;
}

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

int main(){
  int k;
  cin >> k;
  vector<LL> a(k);
  for(int i=0;i<k;i++) cin >> a[i];
  LL ma=2,mi=2;
  for(int i=k-1;i>=0;i--){
    if(ma<a[i]){
      cout << -1 << endl;
      return 0;
    }
    ma=ma/a[i]*a[i]+a[i]-1;
    mi=(mi+a[i]-1)/a[i]*a[i];
  }
  if(mi>ma){
    cout << -1 << endl;
    return 0;
  }
  cout << mi << " " << ma << endl;
  return 0;
}


Measured memory_bytes: 1024
def solve(n, TXY):
    pt, px, py = 0, 0, 0
    for t, x, y in TXY:
        dt = t - pt
        dl = abs(x - px) + abs(y - py)
        if not (dl <= dt and (dt - dl) % 2 == 0):
            # 移動回数が移動時間以下 かつ 余剰時間で場所をキープするには2n回の移動が必要
            return 'No'
        pt, px, py = t, x, y
    return 'Yes'

_n = int(input())
_TXY = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_n, _TXY))

Measured memory_bytes: 27324
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		sc.close();
		switch (s) {
		case "SUN":
			System.out.println(7);
			break;
		case "MON":
			System.out.println(6);
			break;
		case "TUE":
			System.out.println(5);
			break;
		case "WED":
			System.out.println(4);
			break;
		case "THU":
			System.out.println(3);
			break;
		case "FRI":
			System.out.println(2);
			break;
		case "SAT":
			System.out.println(1);
			break;
		}
	}

	public static int[] arrayInt(Scanner sc, int n) {
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		return array;
	}

	public static long[] arrayLong(Scanner sc, int n) {
		long[] array = new long[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextLong();
		}
		return array;
	}

	public static double[] arrayDouble(Scanner sc, int n) {
		double[] array = new double[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextDouble();
		}
		return array;
	}
}


Measured memory_bytes: 22356
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 205;

signed main(void){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	ll K, A, B;
	ll res = 0;
	cin >> K >> A >> B;
	int diff = B - A;
	if (diff <= 2){
		cout << K+1;
		return 0;
	}
	K -= A - 1;
	res = A;
	res += diff * (K / 2) + K % 2;
	cout << res << '\n';
}


Measured memory_bytes: 256
// abc137_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int A, B;
    cin >> A >> B;

    int tmp = max(A+B, A-B);
    int ans = max(tmp, A*B);

    print(ans);

    return 0;
}


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

using namespace std;

int main()
{
    int N, tmp = 1, answer = 0;
    cin >> N;

    vector<int> a(N);
    for (int count = 0; count < N; count++)
    {
        cin >> a.at(count);
    }

    while (true)
    {
        int tmp2 = tmp;
        answer++;
        tmp = a.at(tmp2 - 1);
        a.at(tmp2 - 1) = -1;
        if (tmp == 2)
        {
            break;
        }
        else if (tmp == -1)
        {
            answer = -1;
            break;
        }
    }

    cout << answer << endl;
}

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


/*高速化*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


/* define */
#define ALL(V) (V).begine(),(V).end()
#define SORT(V) sort(ALL(V))
#define REV(V) reverse(ALL(V))
#define RSORT(V) SORT(V);REV(V)
#define SZ(x) ((int)(x).size())
#define rep(i,n) for(int i = 0;i < (int)(n);++i)
#define Rep(i,n) for(int i = 1;i <= (int)(n);++i)
#define Mod(n) n % 1000000007


/* 最大値と最小値に置き換える */
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;}


/* 型定義 */
typedef vector<int> vi;
typedef long long ll;
using Graph = vector<vi>;


/* 定数 */
const double PI = 3.141592;
const double e = 2.6;
const long long Inf = 1LL << 60;
const long long mInf = -Inf;


void calc()
{
    int N;
    cin >> N;
    set<string> item;
    string tmp;
    rep(i,N)
    {
        cin >> tmp;
        item.insert(tmp);
    }
    cout << item.size() << "\n";
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    calc();
}

Measured memory_bytes: 19288
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <tuple>
#include <bitset>
#include <random>
#define REP(i,n) for(int i=0;i<n;i++)
#define INF 100000000000007
using namespace std;
using pii=pair<int,int>;
using LL=int64_t;




int main(){
    int n;
    map<LL,int> L,R;
    
    cin>>n;
    REP(i,n){
        int a;
        cin>>a;
        L[i+a]++;
        R[i-a]++;
    }

    int64_t ans=0;
    for(int x=-n-1;x<2*n+1;x++){
        if(L.count(x)&&R.count(x)){
            ans+=L.at(x)*R.at(x);
        }
        
    }
    cout<<ans<<endl;
    return 0;
}

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


ll  yaku(ll A, ll B) {
	
	if (B == 0) {
		return A;
	}

	yaku(B, A % B);
}


ll bai(ll A, ll B) {
	ll tmp=yaku(A, B);
	return A * B / tmp;
}

int main() {
	ll A, B;
	cin >> A >> B;
	cout<<bai(A , B)<<endl;

}



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

using namespace std;

int main() {
  int64_t N;
  cin >> N;
  vector<int64_t> As(N+1);
  vector<int64_t> Bs(N);
  vector<int64_t> Ds(N+1);
  for (int64_t n = 0; n < N + N; ++n) {
    int64_t i;
    cin >> i;
    if (n < N) {
      ++As[i];
    } else {
      Bs[n % N] = i;
      ++Ds[i];
    }
  }
  for (int64_t n = 1; n <= N; ++n) {
    if (As[n] + Ds[n] > N) {
      cout << "No" << endl; return 0;
    }
    As[n] += As[n-1];
    Ds[n] += Ds[n-1];
  }
  cout << "Yes" << endl;
  
  int64_t mx = 0;
  for (int64_t n = 1; n <= N; ++n) {
    mx = max(mx, As[n] - Ds[n-1]);
  }
  for (int64_t n = 0; n < N; ++n) {
    if (n) cout << " ";
    cout << Bs[(n + N - mx) % N];
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 7956
#include<bits/stdc++.h>
using namespace std;
#define INF INT_MIN
typedef long long int lli;
#define M 100005
lli c[M];
lli v[M];
lli n,W;
lli  mem[105][M];
lli f(lli i,lli w)
{
    if(w<0) return INF;
    if(i==n)
    {
       return 0;
    }

    if(mem[i][w]!=-1)
    {
       return  mem[i][w];
    }

    lli ans1=v[i]+f(i+1,w-c[i]);
    lli ans2=f(i+1,w);
    mem[i][w]=max(ans1,ans2);

    return mem[i][w];

}

int main()
{
  memset(mem,-1,sizeof mem);
  lli i,j;
  cin>>n>>W;
  for(i=0;i<n;i++)
  {
      cin>>c[i]>>v[i];
  }
  lli ans=f(0,W);
  cout<<ans;
}


Measured memory_bytes: 85680
#include <iostream>
using namespace std;
int main(){
char a[2],b[2];
cin>>a>>b;
if(a[0]=='H'){
    if(b[0]=='H')cout<<'H'<<endl;else cout<<'D'<<endl;
}else{
    if(b[0]=='D')cout<<'H'<<endl;else cout<<'D'<<endl;
}
    return  0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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_MAX	2,147,483,647 = 2*1.0e9

int main(){
  int N; cin >> N;
  map<string, ll> cntMap;

  for(int i = 0; i < N; i++){
    string s; cin >> s;
    sort(s.begin(), s.end());
    if(cntMap.find(s) != cntMap.end()){
      cntMap[s] ++;
    } else {
      cntMap[s] = 1;
    }
  }

  ll ans = 0;
  for(auto& kv : cntMap){
    ll cnt = kv.second;
    ans += cnt * (cnt-1) / 2;
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin>>n;
    ll d;
    if(n%2==0)d=n+1;
    else d=n;
    cout<<n*(n-1)/2-n/2<<endl;
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            if(i+j!=d)cout<<i<<" "<<j<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
def main():
    N = int(input())

    tmp = [11, 31, 41, 61, 71, 101, 131, 151, 181, 191, 211, 241, 251, 271, 281, 311, 331, 401, 421, 431, 461, 491, 521, 541, 571, 601, 631, 641, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971, 991, 1021, 1031, 1051, 1061, 1091, 1151, 1171, 1181, 1201, 1231, 1291, 1301, 1321, 1361, 1381]
    for i in range(N-1):
        print(tmp[i], end=" ")
    print(tmp[N-1])

if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
from collections import defaultdict
from itertools import accumulate
n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] + list(accumulate(A))
Q = [ (S[i]-i)%k for i in range(n+1) ]
d = defaultdict(int)
ans = 0
for j in range(n):
  d[Q[j]] += 1
  if j-k+1 >= 0:
    d[Q[j-k+1]] -= 1
  ans += d[Q[j+1]]
print(ans)

Measured memory_bytes: 50536
#include<stdio.h>
int main(void){
	int m,f,r,sum=0;
	
	while(1){
		scanf("%d %d %d",&m,&f,&r);
		if(m==-1&&f==-1&&r==-1){
			break;
		}
		sum=m+f;
		if(m==-1||f==-1){
			printf("F\n");
		}else if(sum>=80){
			printf("A\n");
		}else if(sum<80&&sum>=65){
			printf("B\n");
		}else if((sum<65&&sum>=50)||(sum>=30&&sum<50&&r>=50)){
			printf("C\n");
		}else if(sum<50&&sum>=30){
			printf("D\n");
		}else if(sum<30){
			printf("F\n");
		}
	}
	return 0;
}

Measured memory_bytes: 1836
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
count = B[A[0]-1]
for i in range(1,N):
    count += B[A[i]-1]
    if A[i-1] == A[i] - 1:
        count += C[A[i-1]-1]
print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  string s;cin>>s;
  int n=s.size();

  int mim=INF;
  for(int t=0;t<n-1;t++){
    if(s[t]!=s[t+1]){
      int temp=max(t+1,n-t-1);
      mim=min(mim,temp);
    }
  }

  if(mim==INF){
    cout<<n<<"\n";
  }else{
    cout<<mim<<"\n";
  }
  return 0;
}


Measured memory_bytes: 512
let () = Scanf.scanf "%d %d\n%d %d %d\n%s" @@ fun n k r s p t ->
  let dp =
    Array.init (n + k) @@ fun _ ->
      Array.make 3 0 in
  for i = 0 to n - 1 do
    dp.(i + k).(0) <-
      max dp.(i).(1) dp.(i).(2)
      + if t.[i] = 's' then r else 0;
    dp.(i + k).(1) <-
      max dp.(i).(0) dp.(i).(2)
      + if t.[i] = 'p' then s else 0;
    dp.(i + k).(2) <-
      max dp.(i).(0) dp.(i).(1)
      + if t.[i] = 'r' then p else 0;
  done;
  Printf.printf "%d\n" @@
  Array.fold_left ( + ) 0 @@
  Array.init k @@ fun i ->
    Array.fold_left max min_int dp.(n + i)


Measured memory_bytes: 10240
D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(D)]

L = [0]*26

import copy
MAX_SCORE = -float('inf')
MAX_ANS = -1
for K in range(26):
    v = 0
    ans = [0]*D
    for i in range(1, D+1):
        max_score = -float('inf')
        max_idx = 0
        for j in range(26):
            temp = v
            temp += S[i-1][j]
            L_ = copy.copy(L)
            L_[j] = i
            for k in range(26):
                for l in range(i, min(i+K, D+1)):
                    temp -= C[k]*(i-L_[k])
            if temp >= max_score:
                max_score = temp
                max_idx = j
        v = max_score
        L[max_idx] = i
        ans[i-1] = max_idx+1
    if v >= MAX_SCORE:
        MAX_SCORE = v
        MAX_ANS = ans
print(*MAX_ANS, sep='\n')


Measured memory_bytes: 76348
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char a[5];
	while(cin>>a[0])
	{
		int flag=0;
		for(int i=1;i<4;i++)
		{
			cin>>a[i];
		}
		sort(a,a+4);
		if(a[0]==a[1] && a[2]==a[3] && a[1]!=a[2])
		flag=1;
//		if(a[0]!=a[1] && a[1]==a[2] && a[2]==a[3])
//		flag=1;
//		if(a[0]==a[1] && a[1]==a[2] && a[2]!=a[3])
//		flag=1;
		if(flag)
		cout<<"Yes"<<endl;
		else
		cout<<"No"<<endl;
	}
	return 0;
}

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

typedef long long int ll;
using namespace std;

const ll MOD = 1e9 + 7;

int no_of_steps(int x,int t){
	if(x >= t) return 0;
	else return 1+no_of_steps(2*x,t);
}

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

	double p=0;

	for(int i=1;i<=min(k-1,n);i++){
		int steps = no_of_steps(i,k);
		p += (1.0/pow(2,steps))*(1.0/n);
	}

	if(n >= k) p += ((n-k+1)*(1.0))/n;

	cout << setprecision(9) << p << '\n';
}
















Measured memory_bytes: 512
#include <iostream>

using namespace std;

int main() {
  int N;
  cin >> N;
  if (N == 1) {
    cout << "Hello World" << endl;
    return 0;
  }
  int A, B;
  cin >> A >> B;
  cout << A + B << endl;
  
  return 0;
}


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

def approve(n):
    if (n % 2 == 0):
        if (n % 3 == 0):
            return True
        if (n % 5 == 0):
            return True
        return False
    return True
if (all(list(map(approve, A)))):
    print("APPROVED")
else:
    print("DENIED")


Measured memory_bytes: 2940
use std::io;
use std::cmp;

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

fn search2(
    hist_y: &[usize],
    h:usize,
    w:usize, 
    map: &Vec<Vec<char>>, 
    used: usize
) -> bool {
    let mut used = used;
    for tar in 0..w {
        if used&(1 << tar) > 0 {
            continue;
        }
        used |= 1 << tar;
        let mut found = false;
        for tar2 in tar+1..w {
            if used&(1 << tar2) > 0 {
                continue;
            }
            let mut flag = true;
            for i in 0..h {
                let y1 = hist_y[i];
                let y2 = hist_y[h -1 - i];
                if map[y1][tar]!=map[y2][tar2] {
                    flag = false;
                    break;
                }
            }
            if flag {
                used |= 1 << tar2;
                found = true;
                break;                
            }
        }
        if !found {
            return false;
        }
    }
    return true;
}

fn search1(
    current: usize,
    hist_y: &mut [usize],
    h: usize,
    w: usize,
    map: &Vec<Vec<char>>,
    used: usize
) -> bool {
    if current >= h/2 {
        if h%2 > 0 {
            for tar in 0..h {
                if used&(1 << tar) == 0 {
                    hist_y[h/2] = tar;
                    break;
                }
            }
        }
        if w%2 > 0 {
            for tar in 0..w {
                let mut flag = true;
                for i in 0..h/2 {
                    let y1 = hist_y[i];
                    let y2 = hist_y[h - 1 - i];
                    if map[y1][tar] != map[y2][tar] {
                        flag = false;
                        break;
                    }
                }
                if flag && search2(hist_y, h ,w, map, 1 << tar) {
                    return true;
                }
            }
            return false;
        }
        return search2(hist_y, h ,w, &map, 0)
    }

    for tar in 0..h {
        if used&(1 << tar) > 0 {
            continue;
        }
        for tar2 in tar+1..h {
            if used&(1 << tar2) == 0 {
                hist_y[current] = tar;
                hist_y[h -1 - current] = tar2;
                let nused = used | (1 << tar) | (1 << tar2);
                if search1(current + 1, hist_y, h, w, &map, nused) {
                    return true;
                }
            }
        }
    }
    return false;
}


fn main() {
    let hw:Vec<usize> = read_line().split_whitespace().map(|s| s.parse().unwrap()).collect();
    let (h,w) = (hw[0], hw[1]);
    let map:Vec<Vec<char>> = (0..h).map(|_| read_line().trim().chars().collect()).collect();

    let mut hist_y = vec![0; h];

    if search1(0, &mut hist_y, h, w, &map, 0) {
        println!("YES");
    } else {
        println!("NO");
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;
using P = pair<int, int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef vector<ll> vi;
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
  ll m;
  cin >> m;
  print(48 - m);
}

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

int main()
{
ll a[3][3];
rep(i,9){
  ll b ;
  cin >> b ;
  a[i/3][i%3]=b;
}
ll n ;
cin >> n ;
rep(i,n){
  ll b ;
  cin >> b ;
    rep(i,9){
      if(a[i/3][i%3]==b)a[i/3][i%3]=-1;
    }
}
rep(i,3){
  if(a[0][i]==-1&&a[1][i]==-1&&a[2][i]==-1){
    cout << "Yes" << endl;
    return 0;
  }
}
rep(i,3){
  if(a[i][0]==-1&&a[i][1]==-1&&a[i][2]==-1){
    cout << "Yes" << endl;
    return 0;
  }
}
if(a[0][0]==-1&&a[1][1]==-1&&a[2][2]==-1){
  cout << "Yes" << endl;
  return 0;
}
if(a[2][0]==-1&&a[1][1]==-1&&a[0][2]==-1){
  cout << "Yes" << endl;
  return 0;
}
cout << "No" << endl;
return 0;
}

Measured memory_bytes: 256