akhauriyash/Code-Regression huggingface dataset:
N = int(input())

travel = [[0, 0, 0] for i in range(N+1)]

for i in range(1,N+1):
    t, x, y = map(int, input().split())
    travel[i][0] = t
    travel[i][1] = x
    travel[i][2] = y


for i in range(N):
    x = abs(travel[i+1][1] - travel[i][1])
    y = abs(travel[i+1][2] - travel[i][2])
    t = travel[i+1][0] - travel[i][0]
    if not( x + y  <= t and (t % 2) == ((x + y) % 2)):
        print("No")
        exit()

print("Yes")

Measured memory_bytes: 19572
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
 
const int mx=200010;
const ll mod=1e9+7;

vector<int> dp(mx,-1);
vector<int> v[mx];

int rec(int x){
  if(dp[x]!=-1){ return dp[x]; }
  dp[x]=0;
  for(auto to:v[x]){
    dp[x] = max(dp[x], rec(to)+1);
  }
  return dp[x];
}


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

  rep(i,m){
    int x,y; cin >> x >> y; x--; y--;
    v[x].emplace_back(y);
  }
  
  int ans=0;
  rep(i,n){ ans = max(ans,rec(i)); }
  cout << ans << endl;
  return 0;
}

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


#define             si(a)                   scanf("%d",&a)
#define             sii(a,b)                scanf("%d%d",&a,&b)
#define             siii(a,b,c)             scanf("%d%d%d",&a,&b,&c)
#define             fr(i,n)                 for(int i=0;i<n;i++)
#define             bl                      printf("\n")
#define             inf                     1000000
#define             sz                      110

using namespace std;

char grid[sz][sz];

int main(){
    int h,w,cnt=0;

    sii(h,w);

    fr(i,h){

     scanf("%s",grid[i]);

    }


    fr(i,h){
        fr(j,w){
            if(grid[i][j]=='.') cnt++;
        }

        if(cnt==w){
            fr(k,w) grid[i][k] = 'd';
        }
        cnt = 0;
    }


    fr(i,w){
        fr(j,h){
            if(grid[j][i]=='.' || grid[j][i]=='d') cnt++;
        }

        if(cnt==h){
            fr(k,h) grid[k][i] = 'd';
        }
        cnt = 0;
    }

    fr(i,h){
        fr(j,w){
            if(grid[i][j] !='d'){
                printf("%c",grid[i][j]);
                cnt++;
            }
        }
        if(cnt>0)bl;
        cnt=0;
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			
			int N = scan.nextInt();
			int T = scan.nextInt();
			int []t  = new int[N];
			for(int i  = 0;i<N;i++)t[i] = scan.nextInt();
			int goukei = 0;
			
			for(int i = 0;i<N-1;i++) {
				int s = t[i+1]-t[i];
				if(s<T) {
					goukei+=s;
				}else {
					goukei+=T;
				}
			}
			
			goukei+=T;
			
			System.out.println(goukei);
			
			
		}
		
		
	}
		

}


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

using namespace std;

int cnt[26];

int main(){
	string s;
	cin >> s;
	for(int i = 0; i < s.size(); i++){
		cnt[s[i] - 'a']++;
	}
	int a = 0;
	for(int i = 0; i < 26; i++){
		a += cnt[i] % 2;
	}
	if(a == 0){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

ll n, q, ans[210000];
vector<ll> d[210000];
bool used[210000];

void dfs(ll a) {
	used[a] = true;
	REP(i, d[a].size()) {
		if (!used[d[a][i]]) {
			ans[d[a][i]] += ans[a];
			dfs(d[a][i]);
		}
	}
}
int main() {
	cin >> n >> q;
	REP(i, n - 1) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		d[a].push_back(b);
		d[b].push_back(a);
	}
	REP(i, q) {
		ll a, b;
		cin >> a >> b;
		a--;
		ans[a] += b;
	}
	dfs(0);
	REP(i, n) {
		if (i != 0)cout << " ";
		cout << ans[i];
	}
	cout << endl;
}
	

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

int x[4], y[4];
bool used[4][4];

bool valid(int i, int j) {
    return 0 <= i && i < 4 && 0 <= j && j < 4;
}

int dfs(int i1, int j1) {
    int i2 = (i1*4+j1+1) / 4;
    int j2 = (i1*4+j1+1) % 4;
    if (used[i1][j1]) {
        return i2 < 4 ? dfs(i2, j2) : 1;
    }
    int ret = 0;
    for (int i=0; i<4; ++i) {
        if (valid(i1+y[i], j1+x[i]) && ! used[i1+y[i]][j1+x[i]]) {
            used[i1][j1] = used[i1+y[i]][j1+x[i]] = 1;
            ret += dfs(i2, j2);
            used[i1][j1] = used[i1+y[i]][j1+x[i]] = 0;
        }
    }
    return ret;
}

int main() {
    while (cin >> x[0], x[0] < 4) {
        cin >> y[0] >> x[1] >> y[1] >> x[2] >> y[2] >> x[3] >> y[3];
        cout << dfs(0, 0) << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<functional>

using namespace std;
#define LL unsigned long long
#define MOD 1000000007
#define inf 1999999999


int main() {
	int w, h, a[1005], b[1005];
	cin >> w >> h;
	for (int i = 0; i<w; i++)cin >> a[i];
	for (int i = 0; i<h; i++)cin >> b[i];
	sort(a, a + w);
	reverse(a, a + w);
	sort(b, b + h);
	reverse(b, b + h);
	for (int i = 0; i<w; i++) {
		for (int j = 0; a[i]; j++) {
			if (b[j]) {
				a[i]--;
				b[j]--;
			}
			else {
				cout << 0 << endl;
				return 0;
			}
		}
		sort(b, b + h);
		reverse(b, b + h);
	}
	if(b[0])cout << 0 << endl;
	else cout << 1 << endl;
	return 0;
}



Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  double a[n],b=0;
  for(int i=0;i<n;i++){
    cin >> a[i];
    b+=a[i];
  }
  b/=n;
  double c=99999999;
  for(int i=0;i<n;i++){
    if(c>abs(b-a[i]))c=abs(b-a[i]);
  }
  for(int i=0;i<n;i++){
    if(abs(b-a[i])==c){
      cout << i;
      return 0;
    }
  }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n+1;i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end())
typedef long long ll;
typedef pair<int,int> P;

int main(){
  int H,W;
  cin >>H>>W;
  vector<string> S(H);
  rep(i,H) cin >> S[i];
  int ans[H][W];
  rep(i,H)rep(j,W) ans[i][j] = 0;
  rep(i,H){
    int start = 0;
    int cnt = 0;
    rep(j,W){
      if(S[i][j] == '#'){
        for(int k=start;k<j;k++) ans[i][k] += cnt;
        start = j+1;
        cnt = 0;
      }else{
        cnt ++;
        if(j == W-1){
          for(int k=start;k<=j;k++) ans[i][k] += cnt;
        }
      }
    }
  }
  rep(j,W){
    int start = 0;
    int cnt = 0;
    rep(i,H){
      if(S[i][j] == '#'){
        for(int k=start;k<i;k++) ans[k][j] += cnt;
        start = i+1;
        cnt = 0;
      }else{
        cnt ++;
        if(i == H-1){
          for(int k=start;k<=i;k++) ans[k][j] += cnt;
        }
      }
    }
  }
  rep(i,H) rep(j,W) ans[i][j] = max(ans[i][j]-1,0);
  int maxans = 0;
  rep(i,H) rep(j,W) maxans = max(maxans,ans[i][j]);
  cout << maxans << endl;
}

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


int main()
{
    int h, w, n, big, ans;
    scanf("%d %d %d", &h, &w, &n);

    if(h > w) {
        big = h;
    }
    else {
        big = w;
    }
    if(n > w && n > h) {
        if(n % big == 0){
            ans = n/big;
        }
        else{
            ans = (n/big) + 1;
        }
    }
    else {
        ans = 1;
    }
    printf("%d\n", ans);


}



Measured memory_bytes: 256
#include <stdio.h>

int main(){
    unsigned long long int n, sum = 0;

    scanf("%lld", &n);

    for(int i = 1; i <= n; i++){
        if(i%15 != 0 && i%3 != 0 && i%5 != 0){
            sum += i;
        }
    }
    printf("%lld", sum);
    }

Measured memory_bytes: 1732
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
  
n = int(input())
ans = 0
if n == 1:
    print(0)
else:
    for i in range(len(factorization(n))):
        ch = 1
        loop = 1
        while ch <= factorization(n)[i][1]:
            ans += 1
            loop += 1
            ch = ch + loop

    print(ans)

Measured memory_bytes: 9496
from itertools import combinations
n = int(input())
s = [input() for _ in range(n)]
s = [name for name in s if name[0] in "MARCH"]
s = set(s)
sd = {c:0 for c in "MARCH"}
for c in s:
    sd[c[0]] += 1
res = 0
for l in combinations(sd.values(), 3):
    res += l[0] * l[1] * l[2]
print(res)


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

int main()
{
    int n = 0 ,l[101];
    int ans = 0;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> l[i];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1 ; j < n; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                if (l[i] == l[j] || l[i] == l[k] || l[j] == l[k])
                {
                    continue;
                }
                else if (l[i] + l[j] > l[k] && l[j] + l[k] > l[i] && l[k] + l[i] > l[j])
                {
                    ans++;
                }
                
            }
            
        }
    }
    cout << ans << endl;
}   

Measured memory_bytes: 3552
from itertools import permutations
def main():
    n, m = list(map(int, input().split()))
    G = [set() for _ in range(n)]
    for _ in range(m):
        a, b = list(map(lambda x:int(x) - 1, input().split()))
        G[a].add(b)
        G[b].add(a)
    ans = 0
    for P in permutations(range(1, n)):
        pre = 0
        for p in P:
            if p not in G[pre]:
                break
            pre = p
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9148
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int a = in.nextInt();
            out.println(a + (a * a) + (a * a * a));
        }

    }
}



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

int main() {
    int X;
    cin >> X;
    int N = 6;
    vector<int> prices = {0, 100, 101, 102, 103, 104, 105};
    vector<vector<int>> dp(N + 1, vector<int>(X + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= X; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j - prices[i] >= 0) {
                dp[i][j] = dp[i][j] || dp[i][j - prices[i]];
            }
        }
    }
    bool ans = false;
    for (int i = 1; i <= N; ++i) {
        ans = ans || dp[i][X];
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3328
fun main(args : Array<String>) {
    val n = readLine()!!.toInt()
    val p = readLine()!!.split(" ").map { it.toInt() }
    var count = 0
    (0..(n  - 3)).forEach { i ->
        val one = p[i]
        val two = p[i + 1]
        val three = p[i + 2]

        if ((one < two && two < three) || three < two && two < one) {
            count++
        }
    }

    println(count)
}

Measured memory_bytes: 36072
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(nodes, src):
    """ DFS(木、スタック、重みなし) """

    N = len(nodes)
    stack = [(src, -1, 0)]
    dist = [-1] * N
    while stack:
        u, prev, c = stack.pop()
        dist[u] = c
        for v in nodes[u]:
            if v != prev:
                # 0,1を交互に入れて二部グラフを塗り分け
                stack.append((v, u, 1-c))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for _ in range(N-1):
    a, b = MAP()
    a -= 1; b-= 1
    nodes[a].append(b)
    nodes[b].append(a)

res = dfs(nodes, 0)
cnt0 = res.count(0)
cnt1 = res.count(1)

ans = [0] * N
# グラフの偏りによって場合分け
if cnt0 <= N // 3 or cnt1 <= N // 3:
    if cnt0 > cnt1:
        cnt0, cnt1 = cnt1, cnt0
        res = [1-c for c in res]
    # 少ない方全部に0mod3入れて、多い方は残りを適当に入れる
    p1 = 1
    p2 = 2
    p3 = 3
    for i in range(N):
        if res[i] == 0:
            ans[i] = p3
            p3 += 3
        else:
            if p1 <= N:
                ans[i] = p1
                p1 += 3
            elif p2 <= N:
                ans[i] = p2
                p2 += 3
            else:
                ans[i] = p3
                p3 += 3

else:
    # それぞれに1mod3と2mod3を優先して入れて、なくなったら残りには0mod3を入れる
    p1 = 1
    p2 = 2
    p3 = 3
    for i in range(N):
        if res[i] == 0:
            if p1 <= N:
                ans[i] = p1
                p1 += 3
            else:
                ans[i] = p3
                p3 += 3
        else:
            if p2 <= N:
                ans[i] = p2
                p2 += 3
            else:
                ans[i] = p3
                p3 += 3
print(*ans)


Measured memory_bytes: 54632
#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int N, L, res;
    int sum = 0, tmp, min = 20001;
    cin >> N >> L;
    for(int i = 1; i <= N; i++) sum += L + i - 1; //実際に作れたはずの味
    //1個食べるとき、味の差がもっともちいさくなるようにリンゴを選ぶ
    tmp = sum;
    for(int i = 1; i <= N; i++){
        tmp -= L + i - 1;
        if(abs(sum - tmp) < min){
            min = abs(sum - tmp);
            res = tmp;
        }
        tmp = sum;
    }
    cout << res << endl;
    return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	char ch;
	cin >> ch;
	ch++;
	cout << ch << "\n";

	return 0;
}


Measured memory_bytes: 760
def dfs(i,f):
    if i==n-1:
        return sum(list(map(int,f.split("+"))))

    else:
        return dfs(i+1,f+s[i+1])+dfs(i+1,f+"+"+s[i+1])
s=input()
n=len(s)
print(dfs(0,s[0]))

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <tuple>
#include <functional>
#include <map>
#include <unordered_map>
#include <queue>
#include <tuple>

using namespace std;

#define endl '\n'

using ull = unsigned long int;
using ll = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  const int precision = 13;
  cout.precision(precision);
  cout.setf(ios_base::fixed);

  int n; cin >> n;
  vector<ll> s(3), dp(3);

  cin >> s[1];
  cin >> s[2];

  dp[2] = abs(s[2] - s[1]);

  for (int i = 3; i <= n; ++i) {
    cin >> s[i%3];
    dp[i%3] = min(dp[(i-1)%3] + abs(s[(i-1)%3] - s[i%3]), dp[(i-2)%3] + abs(s[i%3] - s[(i-2)%3]));
  }

  cout << dp[n%3] << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
typedef long long ll;
using namespace std;

const int MAXN = 1e3+5;
const int MOD = 1e9+7;

int main()
{
    int n, h, a, sum = 0;
    scanf("%d%d", &h, &n);
    while (n--)
    {
        scanf("%d", &a);
        sum += a;
    }
    if (sum >= h)
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include<iomanip>

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

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

typedef long long ll;

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout<<setprecision(10);
  ll n,m;
  cin>>n>>m;
  vector<pair<ll,ll>> dri(n);
  rep(i,n)
  {
    ll a,b;
    cin>>a>>b;
    dri[i]={a,b};
  }
  sort(all(dri));
  ll res=0;
  rep(i,n)
  {
    if(m>dri[i].second)
    {
      m-=dri[i].second;
      res+=(ll)dri[i].first*dri[i].second;
    }
    else
    {
      res+=(ll)m*dri[i].first;
      m=0;
      break;
    }
  }
  cout<<res<<endl;


  return 0;

}


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

int main() {
    std::string s;
    int K;
    std::cin >> s >> K;

    std::set<std::string> w;
    for (int i = 0; i < 26; ++i) {
        const char c = 'a' + i;

        for (size_t j = 0; j < s.size(); ++j) {
            if (s[j] == c) {
                for (size_t k = 1; k <= 5; ++k) {
                    if ((j + k) > s.size()) {
                        break;
                    }
                    w.insert(s.substr(j, k));
                }
            }
        }

        if (w.size() >= 5) {
            break;
        }
    }

    int index = 0;
    for (const std::string& str : w) {
        if (index == (K - 1)) {
            std::cout << str << std::endl;
            return 0;
        }

        ++index;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

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

	while ( true )
	{
		int n, q;
		cin >> n >> q;
		if ( !( n | q ) )
		{
			break;
		}

		VI counts( 101, 0 );
		REP( i, 0, n )
		{
			int m;
			cin >> m;
			REP( i, 0, m )
			{
				int d;
				cin >> d;
				counts[d]++;
			}
		}

		int res = 0;
		REP( i, 1, 101 )
		{
			if ( q <= counts[i] && ( res == -1 || counts[ res ] < counts[i] ) )
			{
				res = i;
			}
		}

		cout << res << endl;
	}

	return 0;
}

Measured memory_bytes: 1200
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

int main()
{
    using Grid = std::uint16_t;

    auto h = Grid(0);
    auto w = Grid(0);

    std::cin >> h >> w;

    auto white = Grid(0);
    auto s = std::vector<std::vector<char>>(h, std::vector<char>(w, 0));
    auto visited = std::vector<std::vector<bool>>(h, std::vector<bool>(w, false));
    for (Grid i = 0; i < h; ++i)
        for (Grid j = 0; j < w; ++j)
        {
            std::cin >> s[i][j];
            if (s[i][j] == '.') white++;
        }

    auto q = std::queue<std::tuple<Grid, Grid, Grid>>();

    auto sx = Grid(0);
    auto sy = Grid(0);
    auto gx = Grid(w - 1);
    auto gy = Grid(h - 1);

    auto dx = std::vector<int>({0, 1, 0, -1});
    auto dy = std::vector<int>({1, 0, -1, 0});

    auto goal_steps = std::vector<Grid>();
    visited[sy][sx] = true;
    auto count = Grid(1);
    q.emplace(sx, sy, count);
    while (!q.empty())
    {
        auto px = std::get<0>(q.front());
        auto py = std::get<1>(q.front());
        count = std::get<2>(q.front());
        q.pop();
        for (std::size_t i = 0; i < 4; ++i)
        {
            auto next = count;
            auto tx = Grid(px + dx[i]);
            auto ty = Grid(py + dy[i]);

            if (tx < 0 || w <= tx || ty < 0 || h <= ty) continue;

            if (visited[ty][tx]) continue;

            if (!visited[ty][tx] && s[ty][tx] == '.')
            {
                if (tx == gx && ty == gy)
                {
                    goal_steps.emplace_back(++next);
                    continue;
                }

                visited[ty][tx] = true;
                q.emplace(tx, ty, ++next);
            }
        }
    }

    if (goal_steps.empty())
        std::cout << -1 << std::endl;
    else
        std::cout << white - *std::min_element(goal_steps.begin(), goal_steps.end()) << std::endl;
    return 0;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
Data  = map(int,input().split())
Data2 = [0]*N
for idx,data in enumerate(Data):
    e = data * (data+1) / 2 / data
    Data2[idx] = e
#print(Data2)
sum1 = 0
for i in range(K):
    sum1 += Data2[i]
ans = sum1
for i in range(0,N-K):
    sum1 -= Data2[i]
    sum1 += Data2[i+K]
    if ans < sum1:
        ans = sum1
print(ans)


Measured memory_bytes: 23588
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = getInt(sc);
		String op = getString(sc);
		int b = getInt(sc);
		if (op.equals("+")) {
			System.out.println(a + b);
		} else {
			System.out.println(a - b);
		}
	}

	/**
	 * *汎用メソッド<br>
	 * 入力した配列に対する順列を取得
	 *
	 * @param numArray
	 * @return
	 */
	private static List<Integer[]> getPermutation(int[] numArray) {
		List<Integer[]> permutation = new ArrayList<>();
		Integer[] ans = new Integer[numArray.length];
		boolean[] used = new boolean[numArray.length];

		return buildPermutaion(permutation, numArray, ans, used, 0);
	}

	/**
	 * *汎用メソッド(内部)<br>
	 * 入力した配列に対する順列を作成
	 *
	 * @param list
	 * @param numArray
	 * @param ans
	 * @param used
	 * @param depth
	 * @return
	 */
	private static List<Integer[]> buildPermutaion(List<Integer[]> list, int[] numArray, Integer[] ans, boolean[] used,
			int depth) {

		// 全部使い切った時=>できた順列を返す
		if (depth == numArray.length) {
			list.add(ans.clone());
			return list;
		}
		// 使い切っていない場合

		for (int i = 0; i < numArray.length; i++) {
			if (used[i]) {
				continue;
			}
			ans[depth] = numArray[i];
			used[i] = true;
			list = buildPermutaion(list, numArray, ans, used, depth + 1);

			used[i] = false;
		}

		return list;
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をlongで返却
	 *
	 * @return
	 */
	public static long getLong(Scanner sc) {

		return Long.parseLong(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をintで返却
	 *
	 * @return
	 */
	public static int getInt(Scanner sc) {

		return Integer.parseInt(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をStringで返却
	 *
	 * @return
	 */
	public static String getString(Scanner sc) {

		return sc.next();
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をint配列で返却
	 *
	 * @return
	 */
	public static int[] getIntArray(Scanner sc) {
		String line = "";
		// 直前にnext()を実行していると改行コードだけ取ってしまうのでその対策
		while (line.equals("")) {
			line = sc.nextLine();
		}

		String[] strArray = line.split(" ");
		int[] intArray = new int[strArray.length];
		for (int i = 0; i < strArray.length; i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}

}


Measured memory_bytes: 35580
n = int(input())
s = str(input())
ans = 'Yes'
if len(s) % 2 == 1:
    ans = 'No'
else:
    for i in range(len(s) // 2):
        if s[i] != s[i + len(s) // 2]:
            ans = 'No'
            break

print(ans)

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

int main(){
  int n,w;
  std::cin>>n>>w;
  std::vector<int> values(n+1),weights(n+1);
  for(int i=1;i<n+1;i++) {
    std::cin>>values[i]>>weights[i];
  }

  std::vector<std::vector<int>> table(n+1,std::vector<int>(w+1));
  for(int i=1;i<n+1;i++){
    for(int j=1;j<w+1;j++){
      if(weights[i]<=j){
        table[i][j] = std::max(values[i]+table[i-1][j-weights[i]],table[i-1][j]);
      }else{
        table[i][j] = table[i-1][j];
      }
    }
  }
  std::cout<<table[n][w]<<std::endl;
  return 0;
}

Measured memory_bytes: 6720
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 20000000
map<string,vector<int> > book;
int main()
{
        string s;
        int page;
        while(cin >> s >> page)
        {
                book[s].pb(page);
        }
        for(map<string,vector<int> >::iterator it=book.begin();it!=book.end();it++)
        {
                sort(it->second.begin(),it->second.end());
                cout << it->first << endl;
                for(int i=0;i<(it->second.size());i++)
                {
                        cout << it->second[i];
                        if(i==((it->second.size())-1))
                        {
                                cout << endl;
                        }
                        else
                        {
                                cout << ' ';
                        }
                }
        }
        return 0;
}

Measured memory_bytes: 1244
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n,k;
  cin>>n>>k;
  vector<ll> t(n),d(n),a[100005];
  vector<pair<ll,ll>> p;
  set<ll> s;
  for(int i=0;i<n;i++){
    cin>>t[i]>>d[i];
    p.push_back(make_pair(d[i],t[i]));
  }
  sort(p.begin(),p.end(),greater<pair<ll,ll>>());
  ll c=0;
  priority_queue<ll,vector<ll>,greater<ll>> q;
  for(int i=0;i<k;i++){
    int j=s.size();
    c+=p[i].first;
    s.insert(p[i].second);
    if(j==s.size()) q.push(p[i].first);
  }
  ll m=c+(ll)s.size()*(ll)s.size();
  for(int i=k;i<n;i++){
    if(q.empty()) break;
    int j=s.size();
    s.insert(p[i].second);
    if(j!=s.size()){
      c+=p[i].first;
      c-=q.top();
      q.pop();
      m=max(m,c+(ll)(j+1)*(ll)(j+1));
    }
  }
  cout<<m;
}
  
  


Measured memory_bytes: 9072
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    n = int(input())
    h = list(map(int, input().split()))
    ans = 0
    trial = 0
    t = h[0]
    for i in h[1:]:
        if t >= i:
            trial += 1
            ans = max(ans, trial)
            t = i
        else:
            trial = 0
            t = i
    print(ans)





if __name__=="__main__":
    main()


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

using namespace std;
int main(){
	int n, k;
	scanf("%d%d",&n, &k);
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		if (x >= k) ans++;
	}
	printf("%d\n", ans);
} 

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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

void solve() {
    int n, d;
    cin >> n >> d;

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;

        double x = sqrt(a * a + b * b);
        if (x <= d)ans++;
    }
    cout << ans << endl;
}

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

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 3596
fn readline() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_string()
}
fn readnums() -> Vec<i64> {
    readline().split(" ").map(|x| x.parse().unwrap()).collect()
}

fn main() {
    let (n, k) = match readnums().as_slice() {
        &[n, k, ..] => (n, k),
        _ => (-1, -1),
    };

    let mut pool: std::collections::HashSet<i64> = (1..n + 1).collect();

    for _ in 0..k {
        readline();
        for a in readnums() {
            pool.remove(&a);
        }
    }

    println!("{:?}", pool.len())
}


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

#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
#define ldb long double 
#define db double
#define int long long

#define fr first
#define se second
#define lb lower_bound 
#define ub upper_bound 
#define pb push_back
#define mpr make_pair

#define pi pair<int,int>
#define pdb pair<db,db>
#define pldb pair<ldb,ldb>

#define vi vector<int>
#define vdb vector<db>
#define vldb vector<ldb>
#define vpi vector< pi >

#define mi map<int,int>
#define mdb map<db,db>
#define mldb map<ldb,ldb>


#define forr(a,b) for (int i = (a); i < (b); ++i)
#define rrof(a,b) for (int i = (b)-1; i >= (a); --i)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int md = 1e9+7;
const int MX = 2e5+5;
const int INF = 1e18; 
const ldb PI = 4*atan((ldb)1);

int power_md(int a,int n)
{
 int res=1;
 while(n)
{
 if(n%2)
  res=(res%md*a%md)%md;
  a=(a%md*a%md)%md;
  n/=2;
}
res%=md;
return res;
}

int power(int a,int n)
{
 int res=1;
 while(n)
{
 if(n%2)
  res*=a;
  a=a*a;
  n/=2;
}
return res;
}

int abst(int a)
{
 return ((a<0)?(-1*a):(a));
}

class cmp_set{
public:
	bool operator() (int a, int b){
		return a > b;
	}
};

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

int32_t main()
{
    int a,b;
    cin>>a>>b;
    cout<<(a*b)<<"\n";
    return 0;
}

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

int main() {
  int N, x, y, b, p;
  cin >> N;
  for(int i = 0; i < N; ++i) {
    cin >> x >> y >> b >> p;
    cout << min(x*b+y*p, (x*max(b,5)+y*max(p,2))*4/5) << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>

using namespace std;

int main(void)
{
    long int i,j,n,k,min;
    long int a[200000]={0};
    k=0;
    cin >> n;
    for(i = 1;i <= n;i++)
        cin >> a[i];
    min = a[1];
    for(i = 1;i <= n;i++)
        if(a[i] <= min)
            min = a[i],k++;
    cout << k;
    return 0;
}


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

int main(){
    int x, a;
    int ma = 1;
    cin >> x;

    for(int i = 2; i < x; i++){
        a = i * i;
        while(1){
            if(a > x) break;
            ma = max(ma, a);
            a *= i;
        }
    }

    cout << ma << endl;

    return 0;
}

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

using namespace std;
int main(){
    long n;
    cin >> n;
    long a[n],sum=0;
    for(int i=0; i<n; i++)
      cin >> a[i];
    for(int i=0; i<n; i++)
      sort(a,a+n);
    for(int i=0; i<n; i++){
      cout << a[n-1]-a[0] << endl;
      return 0;
    }
}

Measured memory_bytes: 3588
#pragma comment(linker, "/stack:200000000")
#include <bits/stdc++.h>
#include<string.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define fr(i,s,e) for(i=s;i<e;i++)
#define rf(i,s,e) for(i=s-1;i>=e;i--)
#define pb push_back
#define eb emblace_back
#define mp make_pair
#define ff first
#define ss second
#define int   long long
#define ll   long long
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define vl vector<long long>
#define inf (1LL<<61)
#define vi vector<int> 
#define vii vector< vector<int> >
#define vll vector< vector<long long> >
#define vpi vector< pair<int,int> >   
#define vpl vector< pair<ll,ll> >   
#define viii vector< vector<vector<int> > >
typedef pair<pair<int, int>,int> P;
#define cd complex<double>
#define PI 4*atan(1)
#define mod %1000000007
#define pi 3.14159265358979323846//20 decimals
#define ld long double
#define N 1001

int32_t main()
{
    IOS;
    /*#ifndef ONLINE_JUDGE
    freopen("int.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif*/
    int n;
    cin>>n;
    if(n==1)
    {
        cout<<1<<" "<<1<<endl;;
        cout<<1<<" "<<2<<" "<<0;
        return 0;
    }
    vector<vector<pair<int,int>>> g(21);
    int edges=0;
    int j=1;
    int prev=1;
    while(j*2<=n)
    {
        g[prev].pb(mp(prev+1,j));
        g[prev].pb(mp(prev+1,0));
        edges+=2;
        j=j*2;
        prev++;
    }
   // trace1(prev);
    int node=prev;
    int left=n-1;
    prev=1;
   // trace1(left);
    int cur=n-j;
    if(cur!=0)
    {
        for(int i=0;i<19;i++)
        {
            if(cur & (1<<i))
            {
                g[prev].pb(mp(node,left+1-(1<<(prev-1))));
                left-=(1<<(prev-1));
                edges++;
            }
            prev++;
        }
    }
    assert(node<=20 && edges<=60);
    cout<<node<<" "<<edges<<endl;
    for(int i=1;i<=node;i++)
    {
        for(auto it:g[i])
        {
            cout<<i<<" "<<it.ff<<" "<<it.ss<<endl;
        }
    }
    return 0;
}

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

int main(){
    int k,n;
    cin>>k>>n;
    int a[n];
    for(i=0;i<n;i++)cin>>a[i];
    int ans=a[n-1]-a[0];
    for(i=1;i<n;i++){
    	int attack=k+a[i-1]-a[i];
    	ans=min(ans,attack);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1024
num=input().split(' ')
res=0
for i in range(int(num[0])):
    i=i+1
    s=str(i)
    tmp=0
    for w in s:
        tmp+=int(w)
    if tmp>=int(num[1]) and tmp<=int(num[2]):
        res+=i
print(str(res)+'\n')

Measured memory_bytes: 3060
#include <cstdio>
#include <numeric>
#include <cmath>
#include <iostream>
#include <set>
using i64 = long long;
using namespace std;

const int maxn = 2e5;
const int maxh = maxn;

template <typename T>
class Fenwick {
public:
  T t[maxn + 1] = {0};
  int n;

  Fenwick(int n) : n(n) {}

  T get(int i) {
    T s = 0;
    while (i > 0) {
      s = merge(s, t[i]);
      i -= i & -i;
    }
    return s;
  }

  void update(int i, T v) {
    while (i <= n) {
      t[i] = merge(t[i], v);
      i += i & -i;
    }
  }

  virtual T merge(T a, T b) {
    return a + b;
  }
};

template <typename T>
class MaxFenwick : public Fenwick<T> {
public:
  using Fenwick<T>::Fenwick;
  T merge(T a, T b) override {
    return max(a, b);
  }
};


int n;
int a[maxn + 1];
int h[maxn + 1];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  MaxFenwick<i64> dp(maxh + 1);
  for (int i = 0; i < n; i++) {
    dp.update(h[i], dp.get(h[i]) + a[i]);
  }
  cout << dp.get(n) << '\n';
}


Measured memory_bytes: 3328
/*g++ main.cpp -o main.out*/
/*./main.out*/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

int main()
{
    int n,r;
    cin>>n>>r;
    if(n>=10)cout<<r<<endl;
    else cout<<r+100*(10-n)<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
AB = [list(map(int, input().split())) for _ in range(n)]
C = sorted([(i+j, i, j) for i,j in AB], reverse=True)
ans = 0
for i in range(n):
  s, t, a = C[i]
  if i%2 == 0:
    ans += t
  else:
    ans -= a
print(ans)

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

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

	int n;
	cin>>n;
	deque<ll> q;
	int front = 0;
	for(int i=0; i<n; ++i){
		ll x;
		cin>>x;
		if( front ){ q.push_back(x); }
		else{ q.push_front(x); }
		front = 1 - front;
	}
	vector<int> seq;
	for( auto i : q){
		seq.push_back(i);
	}
	if( front == 0 ){ reverse(seq.begin(), seq.end()); }
	for( auto i : seq ){ cout<<i<<" "; }
	cout<<endl;

	return 0;
}


Measured memory_bytes: 4728
#include<stdio.h>

int judge_min(int a, int b){
    if(b < a){
        return b;

    }else{
        return a;
    }
}

int judge_max(int a, int b){
    if(a < b){
        return b;
    }else{
        return a;
    }
}

int main(void){
    int a, b, c, x, y, sum1 = 0, sum2 = 0, sum3 = 0, min;
    scanf("%d""%d""%d""%d""%d", &a, &b, &c, &x, &y);
    sum1 = a * x + b * y;
    min = judge_min(x, y);
    sum2 = c * min * 2 + a * (x - min) + b * (y - min);
    sum3 = c * judge_max(x, y) * 2;
    printf("%d\n", judge_min(sum3, judge_min(sum1, sum2)));
    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

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

    Scanner sc = new Scanner(System.in);

    int month = sc.nextInt();
    int day = sc.nextInt();

    int tdCounter = 0;

    if (month < 1 || 100 < month || day < 1 || 100 <= day) {
      return;
    }

    for (int i = 1; month >= i; i++) {
      for (int n = 1; day >= n; n++) {
        int tens = n / 10;
        int ones = n % 10;
        if (tens > 1  && ones > 1) {
          if (i == tens * ones) {
            tdCounter++;
          }
        }

      }
    }
    System.out.println(tdCounter);
    return;
  }
}


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

int main()
{
  int n, k;
  cin >> n >> k;
  vector<long long> h(n);
  if (n < k)
  {
    cout << 0 << endl;
    return 0;
  }
  for (int i = 0; i < n; i++)
    cin >> h[i];
  sort(h.begin(), h.end());
  int power = n - k;
  long long cnt = 0;
  for (int i = 0; i < power; i++)
  {
    cnt += h[i];
  }
  
  cout << cnt << endl;
}
    

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll n,k;
  cin >> n >> k;
  vl a(n);
  REP(i,n) cin >> a[i];
  sort(a.begin(),a.end());

  ll ans = 0;
  ll MOD = 1e9+7;

  vl modinv(n+1);
  modinv[1] = 1;
  FOR(i,2,n+1){
    modinv[i] = modinv[MOD%i] * (MOD - MOD/i) % MOD;
  }

  ll ma,mi;
  ll tx = 0;
  ll bx = 0;

  REP(i,n){
    if(i<k-1) mi = 0;
    else if (i==k-1) mi = 1;
    else {
      mi *= i;
      mi %= MOD;
      mi *= modinv[i-(k-1)];
      mi %= MOD;
    }
    if(i==0){
      ma = 1;
      REP(i,k-1){
        ma *= n-i-1;
        ma %= MOD;
        ma *= modinv[i+1];
        ma %= MOD;
      }
    } else if (n-i-1<k-1) ma = 0;
    else {
      ma *= n-i-(k-1);
      ma %= MOD;
      ma *= modinv[n-i];
      ma %= MOD;
    }
    //DEBUG(a[i]);
    //DEBUG(ma);
    //DEBUG(mi);
    bx += a[i] * ma;
    bx %= MOD;
    tx += a[i] * mi;
    tx %= MOD;
  }

  ans = (tx-bx+MOD)%MOD;
  
  //cout << fixed << setprecision(10);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();

        int ans = 0;
        for(int i = 0 ; i < s.length(); i++) {
        	if(s.charAt(i) == t.charAt(i)) {
        		ans++;
        	}
        }
        System.out.println(ans);
	}
}

Measured memory_bytes: 23764
#include <iostream>
using namespace std;
int main(){
	int n,y,m,d,a;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>y>>m>>d;
		a=0;
		for(int j=1;j<y;j++){
			if(j%3==0){
				a=a+200;
			}
			else{
				a=a+195;
			}
		}
		for(int j=1;j<m;j++){
			if(y%3==0||j%2==1){
				a=a+20;
			}
			else{
				a=a+19;
			}
		}
		a=a+d;
		cout<<196471-a<<endl;
	}
    return 0;
}

Measured memory_bytes: 1160
import sys
stdin = sys.stdin
mod = 10**9 + 7

import numpy as np

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

a, b = na()
print("Odd" if a*b % 2 == 1 else "Even")

Measured memory_bytes: 12448
N = int(input())
even = 0
A = []

for i in range(N):
    a = int(input())
    if not a%2:
        even += 1
    A.append(a)

if N == 1:
    print("sfeicrosntd"[(A[0]%2)::2])
elif sum(A) == N:
    print("first")
else:
    if even == N:
        print("second")
    else:
        print("first")

Measured memory_bytes: 7024
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <stack>
#include <string>
#include <deque>
#include <map>
#include <algorithm>

using namespace std;
//--------------------
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

//------------

//-------
void func() {
    int N,M;
    cin >> N >> M ;
    int arr[N];
    for (int j = 0; j < N; ++j) {
        cin >> arr[j];
    }
    long long ans = 0;
    vector<long long> prefixSum(N + 1);
    prefixSum.at(0) = 0;
    for (int k = 0; k < N ; ++k) {
        prefixSum.at(k + 1) = (prefixSum.at(k) + arr[k]) % M;
    }
    map<int ,int> counter;

    for (int i = 0; i <= N; ++i) {
        if(counter.count(prefixSum.at(i))) {
            ans += counter[prefixSum.at(i)];
            counter[prefixSum.at(i)]++;
        } else {
            counter[prefixSum.at(i)] = 1;
        }
    }
    cout << ans << endl;
}

int main() {
    func();
    return 0;
}

Measured memory_bytes: 4352
package main

import (
  "fmt"
  "sort"
)

type pairIntSlice [][2]int
func (p pairIntSlice) Len() int {return len(p)}
func (p pairIntSlice) Less(i, j int) bool {return p[i][0] <= p[j][0]}
func (p pairIntSlice) Swap(i, j int) {p[i], p[j] = p[j], p[i]}

func main() {
  var n, t int
  fmt.Scan(&n, &t)
  ct := make(pairIntSlice, n)
  for i := 0; i < n; i++ {
    fmt.Scan(&ct[i][0], &ct[i][1])
  }
  // sort.Slice(ct, func(i, j int) bool {return ct[i][0] <= ct[j][0]})
  sort.Sort(ct)
  for i := 0; i < n; i++ {
    if ct[i][1] <= t {
      fmt.Println(ct[i][0])
      return
    }
  }
  fmt.Println("TLE") 
}

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

int main(){
  const int mod = 100000;
  int w, h;
  while(std::cin >> w >> h){
    if(w == 0 and h == 0)break;
    int dp[h + 1][w + 1][2];//1 is down, 0 is right
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= w; i++) {
      dp[1][i][0] = 1;
      dp[1][i][1] = 1;
    }
    for (int i = 1; i <= h; i++) {
      dp[i][1][0] = 1;
      dp[i][1][1] = 1;
    }
    for (int i = 2; i <= h; i++) {
      for (int j = 2; j <= w; j++) {
        dp[i][j][0] = (dp[i][j - 1][0] + dp[i - 2][j][1])%mod;
        dp[i][j][1] = (dp[i - 1][j][1] + dp[i][j - 2][0])%mod;
      }
    }
    std::cout << (dp[h - 1][w][1] + dp[h][w - 1][0])%mod << std::endl;

  }
  return 0;
}

Measured memory_bytes: 1244
L, R = list(map(int, input().split()))

Q = L // 2019
l = L - 2019 * Q
r = R - 2019 * Q

if l == 0:
    print(0)
elif 2019 <= r:
    print(0)
else:
    minimum = 2018
    for i in range(l, r):
        for j in range(i+1, r+1):
            val = (i * j) % 2019
            minimum = min(minimum, val)
    print(minimum)

Measured memory_bytes: 3064
if __name__ == '__main__':
	h,w = map(int, input().split())
	while h+w != 0:
		for i in range(h):
			if i%2 == 0:
				if w%2 == 0:
					print("#."*int(w//2))
				else:
					print("#."*int(w//2)+"#")
			else:
				if w%2 == 0:
					print(".#"*int(w//2))
				else:
					print(".#"*int(w//2)+".")
		print()
		h,w = map(int, input().split())


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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin >> a.at(i);
  }
  
  int count=0;
  bool end=true;
  
  while(end){
    for(int i=0;i<N;i++){
      
      if(a.at(i)%2!=0){
        end=false;
        break;
      }
      
      a.at(i)/=2;
      if(i==N-1){
        count++;
      }
      
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3588
#include <iostream>
#include <map>
#include <algorithm>
#include <functional>
#include <sstream>

using namespace std;

int l;

string exchange(const string s)
{
    stringstream s1, s2, ret;
    string tmp;
    int a, b;

    tmp = s;
    sort(tmp.begin(), tmp.end());
    s1 << tmp;
    reverse(tmp.begin(), tmp.end());
    s2 << tmp;
    
    s1 >> a;
    s2 >> b;
    a = b - a;
    ret << a;

    return ret.str();
 }

int main()
{
    string s;

    while (cin >> s >> l, s != "0" || l) {
        map<string, int> m;

        while (s.size() < l)
            s = '0' + s;
        m[s] = 0;

        for (int i = 1; ; i++) {
            s = exchange(s);

            string tmp = s;
            while (tmp.size() < l)
                tmp = '0' + tmp;

            if (m.count(tmp) != 0) {
                cout << m[tmp] << " " << s << " " << i - m[tmp] << endl;
                break;
            }
            else
                m[tmp] = i;
            s = tmp;
        }
    }

    return 0;
}

Measured memory_bytes: 1264