akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define rep(i, n) for (int i = 0; i < n; ++i)
#define debug(s, param) std::cerr << s << param << std::endl;

using namespace std;
using ll = long long;

const ll MOD = 1000000007;

int bfs(const vector<string>& grids, int h, int w) {
  vector<vector<int>> deltas{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  vector<vector<bool>> visit(h, vector<bool>(w, false));
  queue<pair<int, int>> q;
  auto isAvailable = [h, w](int row, int col) { return (row >= 0 && row < h && col >= 0 && col < w); };
  q.emplace(0, 0);
  visit[0][0] = true;
  int steps = 0;
  while (!q.empty()) {
    int size = (int)q.size();
    rep (i, size) {
      int row = q.front().first, col = q.front().second;
      if (row == h - 1 && col == w - 1) return steps;
      q.pop();
      for (const auto& delta : deltas) {
        int nextRow = row + delta[0], nextCol = col + delta[1];
        if (isAvailable(nextRow, nextCol) && grids[nextRow][nextCol] == '.' && !visit[nextRow][nextCol]) {
          visit[nextRow][nextCol] = true;
          q.emplace(nextRow, nextCol);
        }
      }
    }
    ++steps;
  }
  return -1;
}

int main() {
  int h, w;
  cin >> h >> w;
  int blackNums = 0;
  vector<string> grids(h, "");
  rep (i, h) {
    cin >> grids[i];
    rep (j, w) if (grids[i][j] == '#') ++blackNums;
  }
  int res = bfs(grids, h, w);
  if (res == -1) cout << -1 << endl;
  else  cout << h * w - (blackNums + res + 1) << endl;
  return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	ll a,b,n;
	cin>>a>>b>>n;
	ll ans = a*(min(b-1LL,n))/b;
	cout<<ans<<endl;
	return 0;
}

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

int H,W; char s[55][55];
void input()
{
    cin >> H >> W;
    for (int i = 0; i <= H+1; ++i){
        for (int j = 0; j <= W+1; ++j){
            s[i][j] = '.';
        }
    }
    for (int i = 1; i <= H; ++i){
        for (int j = 1; j <= W; ++j){
            cin >> s[i][j];
        }
    }
}

void solve()
{
    bool chk = true;
    for (int i = 1; i <= H; ++i){
        for (int j = 1; j <= W; ++j){
            if (s[i][j] == '.') continue;
            if (s[i-1][j] == '.' && s[i][j-1] == '.' 
            && s[i+1][j] == '.' && s[i][j+1] == '.') {
                chk = false; break;
            }
        }
    }

    if (chk) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    input();
    solve();
    return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<climits>
using namespace std;

vector<vector<int>> D;
vector<vector<int>> c;

int calc(int color, const vector<int> table)
{
	int ret = 0;
	for(int i=0; i<table.size(); i++)
		ret += table[i] * D[i][color];

	return ret;
}

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

	D = vector<vector<int>>(C, vector<int>(C));
	for(int i=0; i<C; i++)
		for(int j=0; j<C; j++)
			cin >> D[i][j];

	c = vector<vector<int>>(N, vector<int>(N));
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			cin >> c[i][j];

	vector<vector<int>> state(3, vector<int>(C));
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			state[(i+j)%3][c[i][j]-1]++;
		}
	}

	int ret = INT_MAX;
	for(int i=0; i<C; i++){
		int aa = calc(i, state[0]);
		for(int j=0; j<C; j++){
			if(j == i)
				continue;

			int bb = calc(j, state[1]);
			for(int k=0; k<C; k++){
				if(k==i || k==j)
					continue;

				int cc = calc(k, state[2]);
				ret = min(ret, aa+bb+cc);
			}
		}
	}

	cout << ret << endl;
	

	return 0;
}


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

int main()
{
	int n;
	cin >> n;
	if (n<1200)
	{
		cout << "ABC" << endl;
	}
	else if (n<2800)
	{
		cout << "ARC" << endl;
	}
	else
	{
		cout << "AGC" << endl;	
	}
	return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>

#define MAX 10000000

long long dp1[MAX];
long long dp2[MAX];

using namespace std;

int main(void)
{
	int n,m,k;
	int i1,i2,i3;
	double ans;
	double poww;

	while(1){
		cin>>n>>m>>k;
		if(n+m+k==0) break;

		for(i1=0;i1<=n*m;i1++){
			dp1[i1]=0;
			dp2[i1]=0;
		}

		for(i1=1;i1<=m;i1++){
			dp1[i1]=1;
		}

		for(i1=1;i1<n;i1++){
			for(i2=1;i2<=n*m;i2++){
				if(dp1[i2]!=0){
					for(i3=1;i3<=m;i3++) dp2[i2+i3]+=dp1[i2];
				}
			}

			for(i2=1;i2<=n*m;i2++){
				dp1[i2]=dp2[i2];
				dp2[i2]=0;
			}
		}

		/*	for(i3=0;i3<=n*m;i3++){
				cout<<i3<<" "<<dp1[i3]<<endl;
			}*/

		ans=0;
		poww=pow((double)m,n);

		for(i1=1;i1<=n*m;i1++){
			if((i1-k)<=0) {
				ans+=(dp1[i1]/poww);
				//cout<<"1 "<<dp1[i1]<<" "<<poww<<endl;
			}
			else {
				ans+=((dp1[i1]/poww)*(double)(i1-k));
				//cout<<i1-k<<" "<<dp1[i1]<<" "<<poww<<endl;
			}
		}

		printf("%.8lf\n",ans);

	}
	return 0;
}

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

#define INPUT freopen("input.txt", "r", stdin);

#define ll long long
#define ld long double

#define len(s) s.size()

#define fl(st, en, in) for (int i = st; i < en; i += in)
#define rfl(st, en, de) for (int i = st; i < en; i -= de)
#define fll fl(0, n, 1)

#define cy cout << "Yes" << endl;
#define cn cout << "No" << endl;
#define ci(s) cin >> s
#define co(s) cout << s << endl

#define vl vector<ll>
#define pb(x) push_back(x)

#define ms(arr, x) memset(arr, x, sizeof(arr))

#define inf INT_MAX

int main()
{
    //INPUT;

    ll n, m;
    ci(n);
    ci(m);
    ll ar[n];
    ll cost[n];
    ll lt[n];
    ll ans = -inf;
    ms(lt, 0);
    fll
    {
        ci(ar[i]);
    }
    fll
    {
        ci(cost[i]);
    }
    fll
    {
        ll st = ar[i];
        ll en = ar[i];
        ll cnt = 0;
        vl vec;
        //co("looping...");
        ll sum = 0;
        while (true)
        {
            sum += cost[st - 1];
            vec.pb(sum);
            ll tm = ar[st - 1];
            cnt++;
            if (tm == en)
            {
                break;
            }
            st = tm;
        }
        lt[i] = cnt; //f
        ll temp_ans = -inf;
        //cout << "count = " << cnt << endl;
        if (m <= cnt)
        {
            fl(0, m, 1)
            {
                temp_ans = max(temp_ans, vec[i]);
            }
        }
        else
        {
            ll d = m / cnt;
            ll r = m % cnt;
            ll chashed = -inf;
            if (vec[len(vec) - 1] >= 0)
            {
                chashed = d * vec[len(vec) - 1];
                temp_ans = chashed;
                fl(0, r, 1)
                {
                    temp_ans = max(temp_ans, vec[i] + chashed);
                }
                ll tm2 = -inf;
                fl(0, cnt, 1)
                {
                    tm2 = max(tm2, vec[i]);
                }
                ll tm3 = chashed;
                fl(0, cnt, 1)
                {
                    tm3 = max(tm3, vec[i] + chashed - vec[len(vec) - 1]);
                }
                temp_ans = max(max(temp_ans, tm2), tm3);
            }
            else
            {
                fl(0, len(vec), 1)
                {
                    temp_ans = max(temp_ans, vec[i]);
                }
            }
        }
        ans = max(ans, temp_ans);

        fl(0, len(vec), 1)
        {
            //cout << vec[i] << " ";
        }
        //cout << endl;
    }
    co(ans);
    //co("Here is the number of elements");
    fll
    {
        // co(lt[i]);
    }
}

Measured memory_bytes: 3796
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A1 = list(map(int, input().split()))
    A2 = list(map(int, input().split()))

    ans = 0
    for i in range(N):
        num = sum(A1[:i + 1] + A2[i:])
        if num > ans:
            ans = num

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
N=int(input())
a=list(map(int,input().split()))
A=[0]*(N+1)
B=sum(a)
for i in range(N):
  A[i+1]=A[i]+a[i]
t=10**15
for i in range(1,N):
  t=min(t,abs(2*A[i]-B))
print(t)

Measured memory_bytes: 23800
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
 
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 (a>b) { a=b; return 1; } return 0; }
#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__)

int main(){
    int a[3];rep(i,3)cin>>a[i];
    int ans=0;
    sort(a,a+3,greater<int>());
    if((a[0]%2==a[1]%2)&&(a[1]%2==a[2]%2)){
        ans=(a[0]-a[1])/2+(a[0]-a[2])/2;
    }
    else if((a[0]%2!=a[1]%2)&&(a[0]%2!=a[2]%2)){
        ans=(a[0]-a[1])/2+(a[0]-a[2])/2;
        ans++;
    }
    else{
        ans=(a[0]-a[1])/2+(a[0]-a[2])/2;
        ans+=2;
    }
    cout<<ans<<endl;
}


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

using namespace std;
int main() {
  int A, B, X, ans = (1<<30);
  cin >> A >> B >> X;
  for ( int a = 0; a <= 20; a++ ){
    for ( int b = 0; b <= 40; b++ ){
      if ( a*1000 + b*500 < X ) continue;
      if ( a*A + b*B < ans ) ans = a*A + b*B;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3112
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = (1e+9)+7;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
char ori[12][12];
char t[12][12];
bool odd; bool even;
int h, w;
bool sym() {
	int used[12] = {};
	int rest = 0;
	if (odd)rest = 1;
	rep(j, w) {
		if (!used[j]) {
			used[j] = 1;
			bool exi = false;
			rep(k, w) {
				if (used[k])continue;
				bool ok = true;
				rep(i, h) {
					if (t[i][j] != t[h - 1 - i][k])ok = false;
				}
				if (ok) {
					used[k] = 1; exi = true; break;
				}
			}
			if (!exi) {
				bool ok = true;
				rep(i, h) {
					if (t[i][j] != t[h - 1 - i][j])ok = false;
				}
				if (ok) {
					if (rest)rest--;
					else return false;
				}
				else return false;
			}
		}
	}
	return true;
}
bool dfs(int x) {
	int nex = -1; int cnt = 0;
	rep(i, h) {
		if (!(x&(1 << i)))cnt++;
		if (nex >= 0)continue;
		if (x&(1 << i)) {
			nex = i; x^=(1 << i);
		}
	}
	if (cnt == h) {
		return sym();
	}
	else {
		bool g = false;
		rep(j, w) {
			t[cnt / 2][j] = ori[nex][j];
		}
		rep(i, h) {
			if (x&(1 << i)) {
				x ^= (1 << i);
				rep(j, w) {
					t[h - 1 - cnt / 2][j] = ori[i][j];
				}
				if (dfs(x))g = true;
				x ^= (1 << i);
			}
		}
		return g;
	}
}
bool solve() {
	int res = (1 << h) - 1;
	if (even) {
		return dfs(res);
	}
	else {
		bool g = false;
		rep(i, h) {
			res ^= (1 << i);
			rep(j, w) {
				t[h / 2][j] = ori[i][j];
			}
			if (dfs(res))g = true;
			res ^= (1 << i);
		}
		return g;
	}
}
int main() {
	cin >> h >> w;
	if (w % 2)odd = true;
	else odd = false;
	if (h % 2)even = false;
	else even = true;
	rep(i, h) {
		string s; cin >> s;
		rep(j, w) {
			ori[i][j] = s[j];
		}
	}
	if (solve())cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, i = nm()
    print(n - i + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9176
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int A = Integer.parseInt(sc.next());
        int B = Integer.parseInt(sc.next());
        int C = Integer.parseInt(sc.next());
        int D = Integer.parseInt(sc.next());
        
        String ret = "";
        if((A + B) == (C + D)){
            ret = "Balanced";
        }
        if((A + B) < (C + D)){
            ret = "Right";
        }
        if((A + B) > (C + D)){
            ret = "Left";
        }
        
        System.out.println(ret);
    }
}

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

int tanku[5] = {5,7,5,7,7};

int main(){
    int n;
    while(scanf("%d",&n), n != 0){
        string w[40];
        for(int i=0;i<n;++i)cin >> w[i];
        for(int i=0;i<n;++i){
            int k=0, cnt=0, j=i;
            while(k < 5 && j < n){
                cnt += w[j].size();
                if(cnt > tanku[k])break;
                if(cnt == tanku[k]){
                    ++k;
                    cnt = 0;
                }
                ++j;
            }
            if(k == 5){
                printf("%d\n",i+1);
                break;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
typedef long long ll;
typedef vector<ll> vl;
#define rp(i, f, t) for (int i = f; i < t; i++)
#define pr(i, f, t) for (int i = t - 1; i >= f; i--)
#define ca(n, a) rp(ca_i, 0, n) cout << a[ca_i] << ((ca_i == n - 1) ? "\n" : " ")
#define za(n, a) rp(za_i, 0, n) a[za_i] = 0
#define be(a) a.begin(), a.end()
int main()
{
    ll k;
    ll kk[] = {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};
    cin >> k;
    cout << kk[k - 1] << endl;
}

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

int main()
{
	list<int> l;


	int nCommand;
	cin >> nCommand;
	
	for (int i = 0; i < nCommand; i++)
	{
		char command[20];
		int key;
		cin >> command;

		if (command[0] == 'i')
		{
			cin >> key;
			l.push_front(key);
		}
		else if (command[6] == 'F') // deleteFirst
			l.pop_front();
		else if (command[6] == 'L') // deleteLast
			l.pop_back();
		else // delete
		{
			cin >> key;
			for ( list<int>::iterator it = l.begin(); it != l.end(); it++)
			{
				if (*it == key)
				{
					l.erase(it);
					break;
				}
			}
		}
	}

	int i = 0;
	for (list<int>::iterator it = l.begin(); it != l.end(); it++)
	{
		if (i++) cout << " ";
		cout << *it;
	}
	cout << endl;

	return 0;
}


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


using namespace std;

int main(){
  int n,m;
  while(cin >> n >> m,n+m){
    vector <int> a;
    for(int i = 0;i < n;i++){
      int s;
      cin >> s;
      a.push_back(s);
    }
    int sum = 0;
    for(int i= 0;i< n;i++){
    for(int j = 0;j < n;j++){
      if(a[i]+a[j] <= m && i != j){
	sum = max(sum,a[i]+a[j]);
      }
    }
    }
    if(sum == 0){
      cout << "NONE" << endl;
  }
    else{
      cout << sum << endl;
    }
  }
}

Measured memory_bytes: 3076
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  ll N;
  cin >> N;
  vector<int> a(N);
  rep(i, N) {
    int x;
    cin >> x;
    ++a[x-1];
  }
  sort(all(a)); // a: frequencies in increasing order.

  vector<int> s(N+1); // s[i]: sum of [0, i). s[0] = 0.
  rep(i, N) {
    s[i+1] = s[i] + a[i];
  }

  for (int k = 1; k <= N; ++k) {
    int l = 0, r = N/k + 1; // [l, r). l:ok r: ng. We want to find the boundary of ok, ng.
    while (l + 1 < r) { // or (r-l > 1)
      int c = (l+r) >> 1;
      bool ok = [&](int c) {
        int i = lower_bound(all(a), c) - a.begin();
        int sum = c*(N-i) + s[i]; // (N-1)-(i-1) = N-i
        return sum >= c*k;
      }(c);
      if (ok) {
        l = c;
      } else {
        r = c;
      }
    }
    cout << l << endl;
  }
}


Measured memory_bytes: 3200
#include<cstdio>
#include<iostream>

using namespace std;

int main(void){

	int t,n;
	int before,now;
	int mup,mdown;

	cin>>t;

	for(int i=0;i<t;i++){
		mup=0,mdown=0;
		cin>>n;
		cin>>before;
		for(int j=1;j<n;j++){
			cin>>now;
			if(now-before>0){
				if(now-before>mup){
					mup=now-before;
				}
			}
			else{
				if(before-now>mdown){
					mdown=before-now;
				}
			}
			before=now;
		}
		cout<<mup<<" "<<mdown<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<vector>

using namespace std;

//全パターン平行移動して全点で等しいか調べる

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

    const int nmax=50;
    char a[nmax][nmax], b[nmax][nmax];

    for(int y=0; y<n; y++) {
        for (int x=0; x<n; x++){
            cin>>a[y][x];
        }
    }
    for(int y=0; y<m; y++) {
        for (int x=0; x<m; x++){
            cin>>b[y][x];
        }
    }

    bool exist=false;
    //a(n*n)がb(m*m)を含むか判定
    for(int ly=0; ly<n; ly++){//bがn*n(a)のフィールドで(ly,lx)平行移動する
        for(int lx=0; lx<n; lx++){
            if(ly+m-1>n || lx+m-1>n)continue;//はみ出たらループ抜ける

            bool match=true;//(ly,lx)平行移動完了→m*mのどこかの点で!=があればfalseにするループ
            for(int y=0; y<m; y++){
                for(int x=0; x<m; x++){
                    if(a[ly+y][lx+x]!=b[y][x])match= false;
                }
            }
            if(match)exist=true;
        }
    }

    if(exist) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}


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

int main() {

	vector<string> c = { "SUN","MON","TUE","WED","THU","FRI","SAT" };
	string s; cin >> s;
	int ans;
	if (s == c[0]) ans = 7;
	if (s == c[1]) ans = 6;
	if (s == c[2]) ans = 5;
	if (s == c[3]) ans = 4;
	if (s == c[4]) ans = 3;
	if (s == c[5]) ans = 2;
	if (s == c[6]) ans = 1;
    cout << ans << endl;
}


Measured memory_bytes: 3592
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>

using namespace std;

const int N = 2e3 + 10;
int a[N];

int main() {
	int n, x, y;
	cin >> n >> x >> y;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
			a[min(i - j, abs(x - j) + abs(y - i) + 1)]++;

	for (int i = 1; i <= n - 1; i++)
		cout << a[i] << endl;

	return 0;
}

Measured memory_bytes: 256
//#include "debug.h"
#include <string.h>
#include <limits.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 200000
typedef long long i64;

int n, k;
i64 a[MAXN], b[MAXN];

int input() {
	if (scanf("%d %d", &n, &k) < 0) return 0;
	for (int i=0; i<n; i++) scanf("%lld", &a[i]);
	return 1;
}

void init() {
}

int inc(map<int, int> &z, int k, int v) {
	auto p = z.find(k);
	if (p == z.end()) {
		if(v) z[k] = v;
		return v;
	}
	else {
		p->second += v;
		if (p->second==0) {
			z.erase(k);
			return 0;
		}
		else return p->second;
	}
}

i64 solve() {
	//multiset.count TLE
	map<int, int> z;
	i64 s = 0;
	int j = k-1;
	if (!j) return 0;
	for (int i=0; i<j && i<n; i++) {
		s = (s + a[i] + k - 1) % k;
		b[i] = s;
		//cout << '=' << s << endl;
		inc(z, s, 1);
	}
	i64 x = 0;
	i64 r = z.find(x)==z.end() ? 0: z[x];
	//cout << '=' << r << ' ' << x << ':' << z << endl;
	for (i64 i=j; i<i64(n)+j; i++) {
		inc(z, b[i-j], -1);
		if (i<n) {
			s = (s + a[i] + k - 1) % k;
			b[i] = s;
			inc(z, s, 1);
		}
		x = (x + a[i-j] + k - 1) % k;
		r += inc(z, x, 0);
		//cout << '=' << r << ' ' << x << ':' << z << '+' << s << '-' << b[i-j] << endl;
	}
	return r;
}

void output(i64 ans) {
	printf("%lld\n", ans);
}

void cleanup() {
}

int main() {
	//precalc();
	//int ca; scanf("%d", &ca);
	while (input()) {
		init();
		output(solve());
		cleanup();
		break;
	}
}




Measured memory_bytes: 12800
/*
 * Created By : pash123
 * 2020-09-13-17.19
*/


#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int M=1e9+7;

int main()
{
    int x;
    cin>>x;
    cout<<(!x);
    return 0;
}


Measured memory_bytes: 3628
#define _CRT_SECURE_NO_WARNINGS
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <array>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <utility>
#include <assert.h>
#include <regex>
#include <numeric>
using namespace std;

typedef unsigned long long ull;
typedef signed long long ll;
#define INF (1LL << 48)

struct PT { ll x; ll y; };
string to_s(ull x) { return to_string(x); }
string to_s(ll x) { return to_string(x); }
ll to_ll(const string& x) { return stoll(x); }
ull to_ull(const string& x) { return stoull(x); }




struct R {
	int id;
	string s;
	int p;
};
bool operator<(const R& a, const R& b)
{
	if (a.s < b.s) return true;
	if (a.s == b.s && a.p > b.p) return true;
	return false;
}

int main(int argc, char* argv[])
{
	for (;;) {
		int N;

		cin >> N;
		if (cin.fail()) break;

		set<R> V;
		for (int i = 0; i < N; i++) {
			R r;
			cin >> r.s >> r.p;
			r.id = i + 1;
			V.insert(r);
		}
		for (auto r : V) {
			cout << r.id << endl;
		}
	}

	return 0;
}


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

#define pb push_back
#define rb  pop_back
#define rf  pop_front
#define ins insert
#define f   first
#define s   second
#define um  unordered_map
#define us  unordered_set
#define pq  priority_queue

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
typedef pair< long long int ,long long int > iil;
typedef long long ll;
typedef vector< ll > vl;
typedef vector< vl > vvl;
typedef vector<double> vd;
typedef pair<double,double> pd;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef us<int> si;
typedef us<double> sd;
typedef us<ll> sll;
typedef vector<vd> md;


const ll MAX = 1e5+5;
const int N = 200043;
const int MOD = 998244353;

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define sz(a) int((a).size())
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for( auto i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define EE '\n'
#define PI 3.14159265
#define g(a,b) a>b?a:b
#define l(a,b) a<b?a:b
#define SOT(A) sort(A.begin(),A.end())
#define SOTR(A) sort(A.rbegin(),A.rend())
#define REV(a) reverse(ALL(a))

// LOOP Control Statements
#define forn(i,j,n) for ( auto i=j ; i<n ; i++ )
#define fornd(i,j,n) for ( auto i=j ; i>n ; i-- )
#define FORE(i, b) for(auto &i:b)


#define SQ(i) (i*i)
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl

#define tcase(term) int tc;cin>>tc;for(int term=0; cout<<EE,term<tc;term++)


int main()
{
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
    // tcase(term)
    {

        vl res(1000001,0);
        int N,W;
        cin>>N>>W;
        ll c,b;
        forn(i,0,N){
        	cin>>c>>b;
        	fornd(j,W,c-1){
        		res[j]=max(res[j],res[j-c]+b);
        	}
        }
        cout<<res[W];

    }
}



Measured memory_bytes: 8064
#include<bits/stdc++.h>
#pragma GCC optimize("O999")
#define long long ll
const int INF = 0x3f3f3f3f;
int maxn=5000005;
using namespace std;
int main()
{
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
    int n;
    cin>>n;
    if(n%2==0)
    {
    	cout<<"0.5000000000";
    	return 0;
	}
	double ans=0;
    ans=1.0*((n+1)/2);
    cout<<fixed<<setprecision(10)<<ans/n<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(long long i=0;i<n;++i)
#define REPP(i,m,n) for(long long i=m;i<n;++i)
#define rep(i,n) for(long long i = n-1;i>=0;--i)
#define repp(i,n,m) for(long long i = n-1; i >= m; --i)
#define ALL(N) (N.begin(),N.end())
#define de cout << "line : " << __LINE__ << " debug" << endl;
#define pb push_back
#define pq priority_queue
#define Dcout(N) cout << setprecision(20) << N << endl
constexpr long long INF = 2147483647;
constexpr long long INFF = 9223372036854775807;

long long N,X;

ll res(long long N,long long X){
    if(N == 0) return 1;
    if(X == 1) return 0;
    long long len = (1LL << (N + 1)) - 3;
    long long pty = (1LL << N) - 1;
    if(X >= 2*len + 3) return 2*pty + 1;
    else if(X <= len + 1) return res(N - 1, X - 1);
    else if(X == len + 2) return pty + 1;
    else if(X < 2*len + 3) return pty + 1 + res(N - 1,X - len - 2);
}

signed main() {
    cin.tie(0);
	ios::sync_with_stdio(false);
    cin >> N >> X;
    cout << res(N,X) << endl;
}


Measured memory_bytes: 256
// Problem: B - Go to Jail
// Contest: AtCoder - AtCoder Beginner Contest 179
// URL: https://atcoder.jp/contests/abc179/tasks/abc179_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define deb(x) cerr << #x << " is " << x << endl;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef long long ll;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

bool f(vii &d) {
    return (d[0].first == d[0].second && d[1].first == d[1].second && d[2].first == d[2].second);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    vii d;
    d.eb(-1, 0);
    d.eb(-1, 0);
    d.eb(-1, 0);
    
    bool ok = false;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        
        d[0] = d[1];
        d[1] = d[2];
        d[2] = {a, b};
        if (f(d)) {
            ok = true;
            break;
        }
    }
    
    if (ok) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    
    cout << endl;
    
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <cmath>
#define rep(i,n) for(int i = 0 ; i < n ; ++i)
#define rep1(i,n) for(int i = 1 ; i <= n ; ++i)
using namespace std;
const int INF = 1e+9;
int n;
int h[100010];
int dp[100010];
int main()
{
  cin >> n;
  rep(i,n) cin >> h[i];
  rep(i,n) dp[i]=INF;
  dp[0]=0;
  rep(i,n-1){
    if(i==n-2) dp[i+1] = min(dp[i+1],dp[i]+abs(h[i]-h[i+1]));
    else{
      dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]));
      dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]));
    }
  }
  cout << dp[n-1] << "\n";
  return 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,i,j,k,l,x,y;
short f[105][105][105][105],ans,s1[105][105],s2[105][105],z;
char s[105][105];
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
	{
		scanf("%s",s[i]+1);
		for(j=1;j<=m;++j)
		{
			s1[i][j]=s1[i][j-1]+(s[i][j]=='o'?1:0);
			if(s[i][j]=='E')
				x=i,y=j;
		}
	}
	for(i=1;i<=m;++i)
		for(j=1;j<=n;++j)
			s2[i][j]=s2[i][j-1]+(s[j][i]=='o'?1:0);
	f[0][0][0][0]=0;
	for(i=0;i<x;++i)
		for(j=0;j<=n-x;++j)
			for(k=0;k<y;++k)
				for(l=0;l<=m-y;++l)
				{
					ans=max(ans,f[i][j][k][l]);
					int lx=j+1,rx=n-i,ly=l+1,ry=m-k;
					//printf("%d %d %d %d  %d   %d %d %d %d\n",i,j,k,l,f[i][j][k][l],lx,rx,ly,ry);
					if(i+1<x)
						f[i+1][j][k][l]=max((int)f[i+1][j][k][l],f[i][j][k][l]+(x-i-1>=lx&&x-i-1<=rx?s1[x-i-1][min(y+l,ry)]-s1[x-i-1][max(y-k,ly)-1]:0));
					if(j+1<=n-x)
						f[i][j+1][k][l]=max((int)f[i][j+1][k][l],f[i][j][k][l]+(x+j+1>=lx&&x+j+1<=rx?s1[x+j+1][min(y+l,ry)]-s1[x+j+1][max(y-k,ly)-1]:0));
					if(k+1<y)
						f[i][j][k+1][l]=max((int)f[i][j][k+1][l],f[i][j][k][l]+(y-k-1>=ly&&y-k-1<=ry?s2[y-k-1][min(x+j,rx)]-s2[y-k-1][max(x-i,lx)-1]:0));
					if(l+1<=m-y)
						f[i][j][k][l+1]=max((int)f[i][j][k][l+1],f[i][j][k][l]+(y+l+1>=ly&&y+l+1<=ry?s2[y+l+1][min(x+j,rx)]-s2[y+l+1][max(x-i,lx)-1]:0));
				}
	printf("%hd",ans);
	return 0;
}


Measured memory_bytes: 205056
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

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

    string S;
    cin >> S;
    int N = S.size();
    vector<int> V(N, 0);
    V.at(0) = (S.at(0) == 'B') ? 1 : 0;
    ll ans = 0;
    for (int i = 1; i < N; ++i) {
        if (S.at(i) == 'B') {
            V.at(i) = V.at(i - 1) + 1;
        } else {
            V.at(i) = V.at(i - 1);
            ans += V.at(i);
        }
    }
    cout << ans << endl;

    return 0;
}

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

int main() {

	int H,W,k;
  string t;
  cin>>H>>W;
  vector<string> S(H);
  for(int i=0;i<H;i++){
    cin>>S.at(i);}
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      k=0;
      if(S.at(i).at(j)!='#'){
        if(i>0&&j>0){if(S.at(i-1).at(j-1)=='#')k++;}
        if(i>0){if(S.at(i-1).at(j)=='#')k++;}
        if(i>0&&j<W-1){if(S.at(i-1).at(j+1)=='#')k++;}
        
        if(j>0){if(S.at(i).at(j-1)=='#')k++;}
        if(j<W-1){if(S.at(i).at(j+1)=='#')k++;}
        
        if(i<H-1&&j>0){if(S.at(i+1).at(j-1)=='#')k++;}
        if(i<H-1){if(S.at(i+1).at(j)=='#')k++;}
        if(i<H-1&&j<W-1){if(S.at(i+1).at(j+1)=='#')k++;}
        t=to_string(k);
        S.at(i).at(j)=t.at(0);}
    }
  }
  for(int i=0; i<H;i++){
     cout<<S.at(i)<<endl;}
}



Measured memory_bytes: 256
io = STDIN

a=[1,3,5,7,8,10,12]
b=[4,6,9,11]
c=[2]
x,y=io.gets.chomp.split.map(&:to_i)
if a.include?(x) && a.include?(y) ||
   b.include?(x) && b.include?(y)
   puts 'Yes'
else
  puts 'No'
end

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

int main(){
    int A,B,C;
    cin >> A >> B >> C;
    int X;
    cin >> X;
    int a = (X/500); //500円玉の最大数
    int result1 = min(a,A);
    int count = 0;
    for(int i = 0; i < result1 + 1; i++){
        //500円玉について
        int X2 = X - 500*i;
        int b = (X2/100);
        int result2 = min(b,B);
        for (int j = 0; j < result2 + 1; j++){
            int X3 = X2 - 100*j;
            int c = (X3/50);
            int result3 = min(c,C);
            if ((500*i + 100* j + 50*result3)== X){
                count += 1;
            }
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main (void)
{
    int i,a=0,k;
    int s;
    int b[2019]={0};
    int l[2019];
    while(1){
        s=getchar();
        if(s==10)break;
        k=s-'0';
        for(i=0;i<2019;i++)l[(i*10+k)%2019]=b[i];
        l[k]++;
        a+=l[0];
        for(i=0;i<2019;i++)b[i]=l[i];
    } 
    printf("%d",a);
}

Measured memory_bytes: 2036
#include<stdio.h>
#define MAX 100005
#define NIL -1
struct Node_struct{int p, l, r;}; /*p: 親(parent), l: 一番左の子(left child), r:右の兄弟(right sibling)*/
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];

void print(int u){
 int i, c;
 printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);

 if(T[u].p == NIL) printf("root, ");
 else if(T[u].l == NIL) printf("leaf, ");
 else printf("internal node, ");

 printf("[");
 for (i=0, c = T[u].l; c != NIL; i++, c = T[c].r){
   if(i) printf(", ");
   printf("%d", c);
 }
 printf("]\n");

}

void calcDepth(int u, int p){
 D[u] = p;
 if(T[u].r!=NIL) calcDepth(T[u].r,p);
 if(T[u].l!=NIL) calcDepth(T[u].l,p+1);
}

int main(){
 int i, j, k;
 int n;
 int id, sib, child;
 int root = NIL;
 scanf("%d", &n);
 for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = NIL;

 for(i=0; i<n; i++){
   scanf("%d %d", &id, &k);
   for(j = 0, sib = NIL; j<k; j++){ //子を入力する (input children)
     scanf("%d", &child);
     T[child].p = id;
     if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
     else T[sib].r = child; //左の兄弟に繋げる (connect to left sibling)
     sib = child;//次の子供の左の兄弟 (the left sibling of the next child)
   }
 }

 //根を求める (find the root)
 for(i=0; i<n; i++){
   if(T[i].p == -1) root = i;
 }

 //それぞれのノードの深さを求める (find depth of each node)
 calcDepth(root, 0);

 //出力 (output)
 for(i=0; i<n; i++) print(i);

 return 0;
}


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

int main(void){
  int n; cin >> n;
  int w[n];
  rep(i,n) cin >> w[i];
  int sum1,sum2;
  int t = 1;
  int mn = 1000000000;
  while(t < n){
    sum1 = 0; sum2 = 0;
    for(int i = 0; i < t; i++){
      sum1 += w[i];
    }
    for(int i = t; i < n; i++){
      sum2 += w[i];
    }
    mn = min(mn,abs(sum1-sum2));
    t++;
  }
  cout << mn << endl;
  return 0;
}


Measured memory_bytes: 256
import itertools
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
p_th = 0
for per in itertools.permutations(range(1, 1+N)):
    p_th += 1
    if P == list(per):
        break

q_th = 0
for per in itertools.permutations(range(1, 1+N)):
    q_th += 1
    if Q == list(per):
        break

print(abs(p_th - q_th))


Measured memory_bytes: 40560
a,b,c = map(int,input().split("/"))

if a<2019:
  print('Heisei')
elif a == 2019:
  if b<4:
    print('Heisei')
  elif b==4:
    if c<=30:
      print('Heisei')
    else:
      print('TBD')
  else:
    print('TBD')
else:
  print('TBD')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define dofloat cout<<fixed<<setprecision(8)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define bitcount __builtin_popcount
#define all(vec) vec.begin(),vec.end()
#define rall(vec) vec.rbegin(),vec.rend()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<long long> vl;
typedef pair<long long,long long> pll;
typedef vector<pair<long long,long long> > vll;
typedef vector<pair<int,int> > vii;
typedef vector<int> vi;
typedef pair<int,int> ii;
const long long MOD=1000000007;
const long long MAX=100005;
const long double PI=3.14159265359;
const long double G=9.807;
const long long INF=1e18;
const long double EPS=1e-6;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
bool isprime(ll a){
  if(a==2)return 1;
  if(!(a&1))return 0;
  for(ll i=3;i*i<=a;i+=2)
    if(a%i==0)return 0;
  return 1;
}
ll mpow(ll base,ll exponent,ll modulus){
  if(modulus==1)return 0;
  long long result = 1;
  base=base%modulus;
  while(exponent){
    if(exponent%2 == 1)
	  result=(result*base)%modulus;
	  exponent=exponent>>1;
	  base=(base*base)%modulus;
  }
  return result;
}
ll minv(ll a,ll mod){
  ll _gcd=gcd(a,mod);
  assert(_gcd==1);
  return mpow(a,mod-2,mod);
}


/*
ll ncr(ll N,ll K){
	if(N<K)return 0;
	if(K==0)return 1;
	if(N==0)return 0;

	ll den=1;
	for(ll i=1;i<=K;i++)den*=i;
	ll num=1;
	while(K--){
		num*=N;
		if(num%den==0){
			num/=den;
			den=1;
		}
		N--;
	}

	return num;
}
*/
ll n;
vll a;
ll ans[2*MAX];
int main(){FAST;
cin>>n;
for(ll i=1;i<=n;i++){
	ll x;cin>>x;
	a.pb({x,i});
}
sort(all(a));
ll eke = a[(n-1)/2].first;
ll kek = a[n/2].first;
for(auto it:a){
	ll x = it.first;
	ll y = it.second;
	if(x<kek){
		ans[y]=kek;
	}
	else{
		ans[y]=eke;
	}
}
for(ll i=1;i<=n;i++){
	cout<<ans[i]<<'\n';
}
return 0;
}

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

using namespace std;

string n;

string dfs(int now, int num)
{
  if (now == 4) {
    if (num == 7) {
      return "=7";
    }
    else {
      return "";
    }
  }
  int add = n[now] - '0';
  string res;
  for (int i = 0; i < 2; i++) {
    switch (i) {
    case 0:
      res = dfs(now + 1, num + add);
      if (res != "") {
        return string("+" + n.substr(now, 1) + res);
      }
    case 1:
      res = dfs(now + 1, num - add);
      if (res != "") {
        return string("-" + n.substr(now, 1) + res);
      }
    }
  }
  return "";
}

void solve()
{
  cin >> n;
  cout << n[0] << dfs(1, (n[0] - '0')) << "\n";
}

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

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

static const int MAX = 200000;

int main() {
  int a,b;
  cin >> a >> b;
  if (a <= b*2) cout << 0 << endl;
  else cout << a - b*2 << endl;
}


Measured memory_bytes: 3536
A, B, C, D, E, F= (int(i) for i in input().split())

dens=0
a=F//100//A
b=F//100//B
c=F//C
d=F//D
for i in range(a+1):
  for j in range(b+1):
    waterA=100*i*A
    waterAB=waterA+100*j*B
    if  waterA<= F and 0 < waterAB <= F:
      for k in range(c+1):
        for l in range(d+1):
          if waterAB+k*C+l*D <= F:
            if k*C+l*D <= (i*A+j*B)*E:
              if dens < (k*C+l*D)/(waterAB+k*C+l*D):
                dens=(k*C+l*D)/(waterAB+k*C+l*D)
                max1=waterAB+k*C+l*D
                max2=k*C+l*D
            else:
              max3=waterAB
              max4=0
if dens>0:
  print(max1,max2)
else:
  print(max3,max4)

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

#define int long long

#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define ALL(v) (v).begin(), (v).end()

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

using pi = pair<int, int>;
using vi = vector<int>;
using vs = vector<string>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vvi = vector<vi>;
using vvb = vector<vb>;

const int INF = 1e16;
const int MOD = 1e9+7;

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; }


signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int N, K; cin >> N >> K;
    vi A(N); REP(i, N) cin >> A[i];
    int ans = 0;
    REP(i, N)
    {
        int t = 0, c = 0;
        REP(j, N)
        {
            if(i < j && A[i] > A[j]) t++;
            if(A[i] > A[j]) c++;
        }
        ans += (t*K)%MOD + (K*(K-1)/2%MOD*c)%MOD;
        ans %= MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int combi(int n)
{
    if (n<2)
        return 0;
    else
        return n * (n - 1) / 2;
}

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d", combi(a) + combi(b));
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <complex>
#include <numeric>
#include <string.h>
#include <random>
#define rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
double PI = 3.141592653589793238462643383279;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

int N;
int x[8], y[8];

int main() {
    cin >> N;
    rep(i,N) cin >> x[i] >> y[i];
    int p[8];
    rep(i,N) p[i] = i;
    double sum = 0.0;
    do {
        rep(i,N-1) {
            sum += sqrt(pow(x[p[i+1]]-x[p[i]],2.0)+pow(y[p[i+1]]-y[p[i]],2.0));
        }
    } while(next_permutation(p, p+N));
    for (int i = 1; i <= N; i++) sum /= i;
    printf("%.9f\n", sum);
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int a = -1;
    int b = -1;
    for(int i = 0; i < s.length() - 1; i++) {
      if(s.charAt(i) == s.charAt(i + 1)) {
        a = i + 1;
        b = i + 2;
      }
    }
    for(int i = 0; i < s.length() - 2; i++) {
      if(s.charAt(i) == s.charAt(i + 2)) {
        a = i + 1;
        b = i + 3;
      }
    }
    System.out.println(a + " " + b);
  }
}

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

using namespace std;

int main() {
	int n, m = 0, r = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int h;
		cin >> h;
		if (m <= h) r++;
		m = max(m, h);
	}
	cout << r << endl;
	return 0;
}


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

typedef long long ll;
const ll mod = 1e9 + 7;

ll modpow(ll a, ll b, ll p = 1e9+7){
    if(b == 0)  return 1;

    if(b % 2 == 0){
        ll d = modpow(a, b/2, p);
        return (d*d) % p;
    }else{
        return (a%p * modpow(a, b-1, p)) % p;
    }
}

struct ModComb{
    vector<ll> po, inv;
    ll N;

    ModComb(ll n) : N(n), po(n), inv(n) {
        po[0] = 1;
        for(int i = 1; i < N; i++)  po[i] = (po[i-1] * i) % mod;
        inv[N-1] = modpow(po[N-1], mod-2, mod);
        for(int i = N-2; i >= 0; i--)   inv[i] = (inv[i+1] * (i+1)) % mod;
    }
    
    ll nCk(ll n, ll k){
        if(k == 0)  return 1;
        if(n < k)   return 0;
        return (((po[n]*inv[n-k])%mod)*inv[k])%mod;
    }

    ll nPk(ll n, ll k){
        if(k == 0)  return 1;
        if(n < k)   return 0;
        return (po[n]*inv[n-k])%mod;
    }

    ll nHk(ll n, ll k){
        if(n == 0 && k == 0)    return 1;
        return nCk(n+k-1, k-1);
    }
};

int main(){
    ModComb mc(2000005);
    auto f = [&](ll x, ll y)->ll{
        ll ret = 0;
        for(int i = 1; i <= x; i++) (ret += mc.nCk(i+1+y, y)) %= mod;
        return ret;
    };
    ll r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    cout << (f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1)+mod+mod)%mod << endl;
    return 0;
}

Measured memory_bytes: 31488
#include <iostream>
#include <string>
#include <vector>
#include <iterator>  // std::ostream_iterator
#include <algorithm> // std::copy
#include <sstream>   // std::stringstream

using namespace std;

void output(vector<int> nums) {
  copy(nums.begin(), nums.end()-1, ostream_iterator<int>(cout, " "));
  cout << nums.back() << endl;
}

int main(int argc, char** argv) {
  vector<int> nums;

  string tmp;

  getline(cin, tmp); // drop 1st line
  getline(cin, tmp); // 2nd line

  stringstream ss(tmp);
  int ti;
  while (ss >> ti) {
    nums.push_back(ti);
  }

  // output(nums);

  int swapcount = 0;

  for (size_t i = 0; i < nums.size(); ++i) {
    for (size_t j = nums.size() - 1; j > i; --j) {
      if (nums[j] < nums[j-1]) {
        int tmp = nums[j];
        nums[j] = nums[j-1];
        nums[j-1] = tmp;
        swapcount++;
      }
    }
  }

  output(nums);
  cout << swapcount << endl;

  return 0;
}




Measured memory_bytes: 3216
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int i,j,k,n,m;
double tab[150][150],len[150][150],ans;

int main(){
	while(scanf("%d %d",&n,&m)*n*m){
		for(i=0;i<n;i++){
			len[0][i]=1;
			for(j=0;j<n;j++){
				scanf("%lf",&tab[i][j]);
			}
		}

		ans=0;

		if(m==1){printf("1.00\n");continue;}

		for(k=1;k<m;k++){
			for(i=0;i<n;i++){
				len[k][i]=0;
				for(j=0;j<n;j++){
					if(len[k][i]<len[k-1][j]*tab[j][i])len[k][i]=len[k-1][j]*tab[j][i];
				}
				if(k==m-1 && ans<len[k][i])ans=len[k][i];
			}
		}

		printf("%.2lf\n",floor(ans*100+0.5)/100);

	}
	return 0;
}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    map<char, int> mp;
    mp['M'] = 0; mp['A'] = 1; mp['R'] = 2; mp['C'] = 3; mp['H'] = 4;
    set<string> st[5];
    int N; cin >> N;
    rep(i, N){
        string S; cin >> S;
        if(mp.count(S[0])){
            st[mp[S[0]]].insert(S);
        }
    }
    ll ans = 0;
    for(int i = 0; i < 5; i++){
        ll sa = st[i].size();
        for(int j = i+1; j < 5; j++){
            ll sb = st[j].size();
            for(int k = j+1; k < 5; k++){
                ll sc = st[k].size();
                ans += sa*sb*sc;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
    string a, b;
    cin >> a;
    cin >> b;
    int cnt = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 3856
#include<stdio.h>
int dp[405][405];
int c[405][405];
int mt(int a,int b)
{
	if(b==0)
	{
		return 1;
	}
	int c=mt(a,b>>1);
	c=(long long)c*c%998244353;
	if(b&1)
	{
		c=(long long)c*a%998244353;
	}
	return c;
}
int pa[512];
int main()
{
	for(int i=0;i<=400;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			c[i][j]=c[i-1][j-1]+c[i-1][j];
			if(c[i][j]>=998244353)
			{
				c[i][j]-=998244353;
			}
		}
	}
	int n;
	scanf("%d",&n);
	dp[0][0]=998244352;
	int sa=0,sb=0;
	while(n--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		b--;
		sa+=a;
		sb+=b;
		pa[0]=1;
		for(int i=1;i<=b;i++)
		{
			pa[i]=(long long)pa[i-1]*a%998244353;
		}
		for(int i=sa;i>=a;i--)
		{
			for(int j=0;j<=sb;j++)
			{
				for(int k=0;k<=b;k++)
				{
					if(k>j)
					{
						break;
					}
					int dec=(long long)c[j][k]*pa[k]%998244353;
					dp[i][j]-=(long long)dp[i-a][j-k]*dec%998244353;
					if(dp[i][j]<0)
					{
						dp[i][j]+=998244353;
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=sa;i++)
	{
		for(int j=0;j<=sb;j++)
		{
			int inc=(long long)dp[i][j]*mt(i,998244352-j)%998244353;
			inc=(long long)inc*sa%998244353;
			inc=(long long)inc*mt(i,998244351)%998244353;
			ans+=inc;
			if(ans>=998244353)
			{
				ans-=998244353;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define endl '\n'
typedef long long LL;
using namespace std;

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

  int t = 1; //cin >> t;
  while (t--){
    int k, a, b; cin >> k >> a >> b;
    int ans = false;
    for (int i = k; i <= b; i += k){
      if (a <= i && i <= b) ans = true;
    }
    cout << (ans ? "OK" : "NG") << endl;
  }
}


Measured memory_bytes: 3636
import statistics
K,N = map(int,input().split())
A = [int(n) for n in input().split()]

a1 = max(A)-min(A)

max_v = 0
A_i = None
for i in range(len(A)-1):
    if (A[i+1]-A[i])>max_v:
        max_v = A[i+1]-A[i]
        A_i = i+1

a2 = A[A_i-1]+abs(K-A[A_i])
print(a2) if a1>a2 else print(a1)

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

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);

    int a, b, h, m;
    cin >> a >> b >> h >> m;

    h = h * 60 + m;
    long double c = 2 * acos(-1);

    long double a1 = -(h * c / 720.0);
    long double a2 = -(m * c / 60.0);

    long double x1 = -(a * sin(a1));
    long double y1 = a * cos(a1);

    long double x2 = -(b * sin(a2));
    long double y2 = b * cos(a2);

//    cout << a1 << " " << a2 << endl;
//
//    cout << x1 << " " << y1 << endl;
//
//    cout << x2 << " " << y2 << endl;

    double ans = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

    printf("%.12f\n", ans);
}


Measured memory_bytes: 4084