akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int main() {
    int N,M;
    while(cin >> N >> M,!(N==0&&M==0)){
        long long h[N+1],w[M+1];
        h[0]=0;
        w[0]=0;
        for (int i=1; i<=N; i++) {
            int k;
            cin >>k;
            h[i]=(h[i-1]+k);
        }
        for (int i=1; i<=M; i++) {
            int l;
            cin >>l;
            w[i]=(w[i-1]+l);
        }
        vector<long long> H((N+1)*(N+1)),W((M+1)*(M+1));
        for (int i=0; i<H.size(); i++) {
            H[i]=1000000007;
        }
        for (int i=0; i<W.size(); i++) {
            W[i]=1000000007;
        }
        int p=0;
        for (int i=0; i<N; i++) {
            for (int j=i+1; j<=N; j++) {
                if (h[i]<h[j]) {
                    H[p]=h[j]-h[i];
              //      cout << H[p]<<endl;
                    p++;
                }
            }
        }
        //cout << "^^^^";
        sort(H.begin(), H.end());
        int q=0;
        for (int i=0; i<M; i++) {
            for (int j=i+1; j<=M; j++) {
                if (w[i]<w[j]) {
                    W[q]=w[j]-w[i];
                 //   cout << W[q]<<endl;
                    q++;
                }
            }
        }
       // cout << "----";
        sort(W.begin(), W.end());
        for (int i=0;i<N; i++) {
           // cout << W[i]<<",";
        }
       // cout <<endl;
        for (int i=0;i<M; i++) {
           // cout << H[i];
        }
        //cout <<endl;
        long long ans=0;
        int flag=0;
        for (int i=0; i<p; i++) {
            for (int j=flag; W[j]<=H[i]&&j<q; j++) {
                if (W[j]==H[i]) {
                    ans++;
                }
                if (W[j]<H[i]) {
                    flag++;
                }
            }
        }
        cout << ans <<endl;
    }
    return 0;
}

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

int main()
{
	int n,t,i,j,k;
	long int a[100001], d[100001];
	cin>>n;

	for(i=0;i<n;i++)
	{
		scanf("%ld", &a[i]);
	}

	long ans = 0;
	d[0] = 0;
	d[1] = abs(a[1]-a[0]);
	for(i=2;i<n;i++)
	{
		d[i] = min(d[i-1]  + abs(a[i] - a[i-1]) , d[i-2] + abs(a[i]-a[i-2]));
	}
	cout<<d[n-1]<<endl;

	return 0;

}

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

int f(int n){
  if(n%2==0)
    return n/2;
  return n*3+1;
}
int main(){
  int n;
  cin >> n;
  vector<int>hen(n);
  for(int i=0;i<n;i++)
    cin >> hen.at(i);
  sort(hen.begin(),hen.end(),greater());
  int a=0;
  for(int i=1;i<n;i++)
    a+=hen.at(i);
  cout << ((hen.at(0)<a)?"Yes":"No") << endl;
  return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define rep(i, init, n) for(int i = init; i <(int)(n); i++)

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

ll MOD = pow(10, 9) + 7;

ll powmod(ll a, ll p, ll MOD) {
	ll ans = 1;
	ll mul = a;
	for (; p > 0; p >>= 1, mul = (mul * mul) % MOD) {
		if ((p & 1) == 1)ans = (ans * mul) % MOD;
	}
	return ans;
}

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> v(K+1, 0);
    for(ll i = K; i > 0; i--){
        ll tmp = K / i;
        ll hoge = powmod(tmp, N, MOD) % MOD;
        for(ll j = 2*i; j <= K; j+=i) hoge =  (hoge - v[j] + MOD) % MOD;
        v[i] = hoge;
    }
    ll ans = 0;
    REP(i, K+1) {
        ll tmp = (i * v[i]) % MOD;
        ans = (ans + tmp) % MOD;
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define ll long long
using namespace std;
	bool a[11];
int main(){
	ll n,m,x;
	cin>>n>>m;
	//for(int i:a)
		///cout<<i<<" ";
	
	for(int i=0;i<m;i++)
	{cin>>x;a[x]=1;}
	for(int i=n;;i++){
		bool p=true;
		string s = to_string(i);
		for(int j=0;j<s.size();j++){
			if(a[char(s[j])-'0']==1)
			{p=0;break;}
		}
		if(p==1)
		{cout<<i;break;}
	}
	return 0;
}



Measured memory_bytes: 256
import heapq
N, W = [int(n) for n in input().split()]
tmpw = 0
tmpv = 0
minheap = []
for i in range(N):
    w, v = [int(n) for n in input().split()]
    if(w < 0):
        tmpw += w
        tmpv += v
        w *= -1
        v *= -1
    if(v > 0):
        if w == 0:
            tmpv += v
        else:
            heapq.heappush(minheap, (-(v/w), w, v))
while(W-tmpw > 1e-9 and not minheap == []):
    p = heapq.heappop(minheap)
    w = p[1]
    v = p[2]
    x = min(1, (W-tmpw)/w)
    tmpw += x*w
    tmpv += x*v
print(tmpv)



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

ll gcd(ll a, ll b){
    if(a < b) return gcd(b, a);
    ll r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

ll nck(ll n, ll k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  if(k == 0 || k == n) return 1;
  ll nume = 1, deno = 1;
  for(int i=0; i<k; i++){
    nume *= (n-i);
    deno *= (i+1);
    ll g = gcd(nume, deno);
    nume /= g;
    deno /= g;
  }
  return (ll)(nume/deno);
}


int main(){
    ll N, A, B;
    cin >> N >> A >> B;
    vector<double> v(N);
    rep(i, 0, N) cin >> v[i];
    sort(v.begin(), v.end(), greater<double>());
    double ave = 0;
    rep(i, 0, A) ave += v[i];
    ave /= A;
    ll sum = 0, sA = 0;
    rep(i, 0, N){
        if(v[i] == v[A-1]){
            sum++;
            if(i < A) sA++;
        }
    }
    cerr << "sum : " << sum << endl;
    cerr << "sA  : " << sA << endl;
    ll ans = 0;
    if(sA == A){
        rep(i, A, B+1){
            ans += nck(sum, sA);
            sA++;
        }
    }else{
        ans = nck(sum, sA);
    }
    printf("%.6lf\n", ave);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        Console.WriteLine(Solve());
        //Solve();
        return;
    }

    public static string Solve()
    {
        int[] input = ReadInts();
        int N = input[0];
        int R = input[1];
        int ans;
        if (N > 10)
        {
            ans = R;
        }
        else
        {
            ans = R + 100 * (10 - N);
        }


        return ans.ToString();
    }

    private static string Read() { return Console.ReadLine(); }
    private static int ReadInt() { return int.Parse(Read()); }
    private static long ReadLong() { return long.Parse(Read()); }
    private static double ReadDouble() { return double.Parse(Read()); }
    private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
    private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
    private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
}


Measured memory_bytes: 11092
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int tlim = sc.nextInt();
    int[] c = new int[n];
    int[] t = new int[n];
    for(int i = 0;i<n;i++){
      c[i] = sc.nextInt();
      t[i] = sc.nextInt();
    }
    int min = 1001;
    for(int i = 0;i<n;i++){
      if(t[i]<=tlim){
        min = Math.min(c[i],min);
      }
    }
    if(min>1000){
      System.out.println("TLE");
    }else{
      System.out.println(min);
    }
  }
}


Measured memory_bytes: 35916
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, Z, W;
	cin >> N >> Z >> W;

	vector<Int> a(N);
	for (Int i = 0; i < N; i++) {
		cin >> a[i];
	}


	//Int ans = abs(Z - W);

	//Xが全部取る場合
	Int ans = abs(a[N - 1] - W);

	//Xが最後の一枚をYに残す場合
	if (N>1) {
		ans = max(ans, abs(a[N - 1] - a[N - 2]));
	}
	cout << ans << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int A,B,C,D;
  1<=(A,B,C,D)<=10;
  cin>>A>>B>>C>>D;
  if(A+B>C+D){
    cout<<"Left"<<endl;
  }
  else if(A+B==C+D){
    cout<<"Balanced"<<endl;
  }
  else{
    cout<<"Right"<<endl;
  }
}
  

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <cstdio>
using namespace std;
double x[200],y[200],z[200],vx[200],vy[200],vz[200],r[200],vr[200];
int n;
double t[200];

typedef pair<double,pair<int,int> > P;

double f(double u,int i,int j){
  double dx = (x[i]+vx[i]*u)-(x[j]+vx[j]*u);
  double dy = (y[i]+vy[i]*u)-(y[j]+vy[j]*u);
  double dz = (z[i]+vz[i]*u)-(z[j]+vz[j]*u);
  return sqrt(dx*dx+dy*dy+dz*dz)-(r[i]-vr[i]*u)-(r[j]-vr[j]*u);
}

double outtime(int i,int j){
  double right=0,left=min(t[i],t[j]);
  for(int loop = 0; loop < 100; ++loop){
    if(f((left*2+right)/3,i,j)<f((left+right*2)/3,i,j))
      right = (left+right*2)/3;
    else
      left = (left*2+right)/3;
  }
  double T = (right+left)*0.5;
  if(f(T,i,j)>0) return 1000;
  double low = 0, high = T;
  for(int k=0;k<70;++k){
    double mid = (low+high)*0.5;
    if(f(mid,i,j)>=0) low = mid;
    else high = mid;
  }
  return (low+high)*0.5;
}

int main(){
  while(scanf("%d",&n),n){
    vector<P> event;
    bool out[200] = {};
    
    for(int i=0;i<n;++i)
      cin>>x[i]>>y[i]>>z[i]>>vx[i]>>vy[i]>>vz[i]>>r[i]>>vr[i];
    for(int i=0;i<n;++i){
      t[i] = r[i]/vr[i];
      event.push_back(P(t[i],make_pair<int,int>(i,i)));
    }

    for(int i=0;i<n;++i)
      for(int j=i+1;j<n;++j){
	double T = outtime(i,j);
	event.push_back(P(T,make_pair<int,int>(i,j)));
      }
    sort(event.begin(),event.end());

    int m = event.size();
    double cur;
    for(int i=0;i<m;++i){
      cur = event[i].first;
      int a = event[i].second.first;
      int b = event[i].second.second;
      if(!out[a] && !out[b]){
	t[a]=t[b]=cur;
	out[a]=out[b]=true;
      }
    }

    for(int i=0;i<n;++i) printf("%.10lf\n",t[i]);

  }
  return 0;
}

Measured memory_bytes: 1944
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector < long long > vll;
typedef pair < long long, long long > pll;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector<vector<int>> vvi;
#define deb(x) cout << #x << " : " << x << endl
#define deb2(x , y) cout << #x << " : " << x << " , "<< #y << " : " << y << endl
#define debv(x) for(auto i=x.begin();i!=x.end();i++) cout<<*i<<' ';cout<<endl
#define debp(x) for(auto i=x.begin();i!=x.end();i++) cout<<i->first<<':'<<i->second<<' ';cout<<endl
#define debvv(x) for(auto j=x.begin();j!=x.end();j++) { for(auto i=(*j).begin();i!=(*j).end();i++) cout<<*i<<' ';cout<<endl;}cout<<endl
#define rsz(x,n) x.clear(); x.resize(n)
#define rrsz(x,a,n) x.clear(); x.resize(n,a)
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,a,n) for(int i = a; i < n; i++)
#define wt while(true)
#define all(x) x.begin(),x.end()
#define pb push_back
#define csl ios_base::sync_with_stdio(false); cin.tie(NULL)
#define INF (1e9 + 7)
#define endl '\n'
int mod=1e9+7;

void solve() {
	int n,m;
	cin>>n>>m;
	vector<string> arr(n);
	vvi paths(n,vi(m,0));
	rep(i,n){
		cin>>arr[i];
	}
	paths[0][0]=1;
	rep(i,n){
		rep(j,m){
			if(j!=m-1 && arr[i][j+1]=='.'){
				paths[i][j+1]+=paths[i][j];
				paths[i][j+1]%=mod;
			}
			if(i!=n-1 && arr[i+1][j]=='.'){
				paths[i+1][j]+=paths[i][j];
				paths[i+1][j]%=mod;
			}
		}
	}
	cout<<paths[n-1][m-1]<<endl;
}

int main() {
	csl;
	int testcase=1;
//	cin >> testcase;
	for (int i = 0; i < testcase; i++) {
		solve();
	}
	return 0;
}



Measured memory_bytes: 8556
#include<iostream>
using namespace std;
int main()
{
int a,b,c,k;
cin >> a >> b >> c;
cin >> k;
if(b>a && c>b)
cout << "Yes" << endl;
else {
if(b<=a){
while(b<=a){
b*=2;
k--;
}
}
if(k>=0 && b<c)
cout << "Yes" << endl;
else{
if(c<=b){
while(c<=b){
c*=2;
k--;
}
}
if(k>=0)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}

return 0;
}


Measured memory_bytes: 3612
#include <iostream>

int main()
{
        int n, money = 100000;
        std::cin >> n;
        while(n--)
                money += money*5/100, money = (money / 1000 + ((money % 1000)?(1):(0))) * 1000;
        std::cout << money << std::endl;
        return 0;
}

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

struct Node {
    int parent;
    int left;
    int right;
};

void CalcParent(Node *node_list, int n)
{
    for (int i = 0; i < n; i++) {
        // i is target node id
        int left = node_list[i].left;
        int right = node_list[i].right;
        if (left != -1) {
            node_list[left].parent = i;
        }
        if (right != -1) {
            node_list[right].parent = i;
        }
    }
}

int GetSibling(int id, Node *node_list)
{
    int parent = node_list[id].parent;
    if (parent == -1) {
        return -1;
    } else {
        if (node_list[parent].right == id) {
            return node_list[parent].left;
        } else {
            return node_list[parent].right;
        }
    }
}

int GetDegree(int id, Node *node_list)
{
    int degree = 0;
    if (node_list[id].left != -1)  degree++;
    if (node_list[id].right != -1) degree++;
    return degree;
}

int GetDepth(int id, Node *node_list)
{
    int depth = 0;
    int target_id = id;
    while (node_list[target_id].parent != -1) {
        depth++;
        target_id = node_list[target_id].parent;
    }
    return depth;
}

int GetHeight(int id, Node *node_list)
{
    int height_l = 0, height_r = 0;
    if (node_list[id].left != -1) {
        height_l = 1;
        height_l += GetHeight(node_list[id].left, node_list);
    }
    if (node_list[id].right != -1) {
        height_r = 1;
        height_r += GetHeight(node_list[id].right, node_list);
    }

    if (height_l > height_r) {
        return height_l;
    } else {
        return height_r;
    }
}

std::string GetType(int id, Node *node_list)
{
    std::string type;

    if (node_list[id].parent == -1) {
        type = "root";
    } else if (node_list[id].right == -1 && node_list[id].left == -1) {
        type = "leaf";
    } else {
        type = "internal node";
    }
    return type;
}

int main(int argc, char *argv[])
{
    int n;
    scanf("%d", &n);

    // Init
    Node *node_list = (Node *)malloc(sizeof(Node) * n);
    for (int i = 0; i < n; i++) {
        node_list[i].parent = -1;
        node_list[i].left = -1;
        node_list[i].right = -1;
    }

    // Make node_list
    for (int i = 0; i < n; i++) {
        int id, left, right;
        scanf("%d", &id);
        scanf("%d", &left);
        scanf("%d", &right);
        node_list[id].left = left;
        node_list[id].right = right;
    }
    CalcParent(node_list, n);

    // Dump node_list info
    for (int i = 0; i < n; i++) {
        std::cout << "node " << i << ": ";
        std::cout << "parent = " << node_list[i].parent << ", ";
        std::cout << "sibling = " << GetSibling(i, node_list) << ", ";
        std::cout << "degree = " << GetDegree(i, node_list) << ", ";
        std::cout << "depth = " << GetDepth(i, node_list) << ", ";
        std::cout << "height = " << GetHeight(i, node_list) << ", ";
        std::cout << GetType(i, node_list) << std::endl;
    }

    // Free node_list
    free(node_list);
    return 0;
}


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

int main(){
  string S;
  int64_t K0;
  int K;
  cin >> S >> K0;
  if(K0>110){
    K=110;
  }
  else{
    K=(int)K0;
  }
  int L=S.size();
  int F=0;
  for(int i=0; i<L; i++){
    if(S.at(i)!='1'){
      F=i+1;
      break;
    }
  }
  if(K<F){
    cout << 1 << endl;
  }
  else if(F!=0){
    cout << S.at(F-1) << endl;
  }
  else{
    cout << 1 << endl;
  }
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll n; cin >> n;
  map<ll,ll> difftable; map<ll,ll> protable;
  
  rep(i,n){
    ll x; cin >> x;
    difftable[x]++;
  }
  
  ll m; cin >> m; 
  rep(i,m){
    ll x; cin >> x;
    protable[x]++;
  }
  
  bool flag = true;
  for(auto p : protable){
    ll num = p.first; ll cnt = p.second;
    if(difftable[num] < cnt){
      flag = false;
      break;
    }
  }
  
  if(flag) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  
}

Measured memory_bytes: 28496
package main

// Solution for https://atcoder.jp/contests/abc070/tasks/abc070_a

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

type contest struct {
	in  io.Reader
	out io.Writer
}

func (con *contest) Scan(a ...interface{}) (int, error) {
	return fmt.Fscan(con.in, a...)
}
func (con *contest) Scanln(a ...interface{}) (int, error) {
	return fmt.Fscanln(con.in, a...)
}
func (con *contest) Scanf(f string, a ...interface{}) (int, error) {
	return fmt.Fscanf(con.in, f, a...)
}
func (con *contest) Print(a ...interface{}) (int, error) {
	return fmt.Fprint(con.out, a...)
}
func (con *contest) Println(a ...interface{}) (int, error) {
	return fmt.Fprintln(con.out, a...)
}
func (con *contest) Printf(f string, a ...interface{}) (int, error) {
	return fmt.Fprintf(con.out, f, a...)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	con := &contest{in: in, out: out}
	con.main()
}

func (con *contest) main() error {
	var n int
	con.Scan(&n)
	if n/100 == n%10 {
		con.Println("Yes")
	} else {
		con.Println("No")
	}
	return nil
}


Measured memory_bytes: 1848
import java.util.Scanner;

public class Main {
	public static void main(String []args){
		//????????£?????????????????????
		Scanner sc = new Scanner(System.in);
		//
		//??????????????????
		String word = sc.nextLine();
		//????????????????????????????????´???
		String W = "";
		String R = "";
		for(int i = 0; i<word.length(); i++){
			//???????????????1??????????????????
			W = word.substring(i, i + 1);
			//System.out.println(i + "=" + W);
			//?????¶??? ?°???????????£???????
			if(W.equals(W.toLowerCase())){
			//?°????????????£????????§??????????????´
				W =W.toUpperCase();
				//?????¶??? ??§??????????£???????
			}else if (W.equals(W.toUpperCase())){
			//??§???????????£???????°???????????????´
				W = W.toLowerCase();
			}
			//???????????£???????????????????????????
			R += W;
		}
		//???????????¨???
		System.out.println(R);
	}
}

Measured memory_bytes: 31812
#include <bits/stdc++.h>
#include <string>
#define ft first
#define sc second
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) (a)=max(a, b)
#define chmin(a, b) (a)=min(a, b)
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;


/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/

ll moP(ll x, ll n) {
  ll res=1;
  while(n>0) {
    if(n&1) moC(res, *, x);
    moC(x, *, x);
    n>>=1;
  }
  return res;
}


int main() {
  ll i, j, k;
  
  ll N, K;
  cin >> N >> K;
  
  ll ans=0;
  for(i=K; i<=N+1; i++) {
    ll t=N-i+1;
    ll ma=i*(t+N)/2;
    ll mi=i*(i-1)/2;
    
    moC(ans, +, ma-mi+1+MOD);
  }
  
  pt(ans);
  
  
  
}




Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main implements Closeable {

  private InputReader in = new InputReader(System.in);
  private PrintWriter out = new PrintWriter(System.out);

  public void solve() {
    n = in.ni();
    for (int i = 0; i < n; i++) {
      children.add(new Child(i, in.ni()));
    }
    children.sort(Comparator.comparingLong(c -> -c.activeness));
    dp = new Long[n][n];
    out.println(recurse(0, 0));
  }

  private class Child {
    private int pos;
    private long activeness;

    private Child(int pos, long activeness) {
      this.pos = pos;
      this.activeness = activeness;
    }
  }

  private int n;
  private List<Child> children = new ArrayList<>();
  private Long[][] dp;

  private long recurse (int idx, int left) {
    if (idx == n) return 0;

    if (dp[idx][left] != null) return dp[idx][left];

    int position = children.get(idx).pos;
    long activeness = children.get(idx).activeness;
    int right = n - 1 - (idx - left);
    //place on the left
    int d1 = Math.abs(position - left);
    long ans = d1 * activeness + recurse(idx + 1, left + 1);

    //place on the right
    int d2 = Math.abs(right - position);
    ans = Math.max(ans, d2 * activeness + recurse(idx + 1, left));

    return dp[idx][left] = ans;
  }

  @Override
  public void close() throws IOException {
    in.close();
    out.close();
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int ni() {
      return Integer.parseInt(next());
    }

    public long nl() {
      return Long.parseLong(next());
    }

    public void close() throws IOException {
      reader.close();
    }
  }

  public static void main(String[] args) throws IOException {
    try (Main instance = new Main()) {
      instance.solve();
    }
  }
}


Measured memory_bytes: 107940
/*
How to lambda
  ex) sort(ALL(cont),[](dat a,dat b){return a.l<b.l;});
lower_bound/upper_bound
  1 2 2 2 3 3 
    ^lb   ^ub */
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define BR "\n"
#define REP(i,n) for(int (i)=0;(i)<(n);++(i))
#define ALL(cont) begin(cont),end(cont)
#define AS_MOD(a,b) ((((a) % (b) ) + (b)) % (b))
#define FEACH(it,cont) for(auto (it) = begin(cont); it!=end(cont);++it)
#define FEACHR(it,cont) for(auto (it) = rbegin(cont); it!=rend(cont);++it)
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define getll() ([](){ll s;scanf("%lld", &s);return s;})()
#define getld() ([](){ld s;scanf("%Lf", &s);return s;})()
#define prl(P) printf("%lld", P)
#define prd(P) printf("%.10Lf", P)
#define pr(P) printf(P)
#define assign_if_greater(V, T) V=max(V,T)
using namespace std;
typedef long long ll;
typedef long double ld;
int A,B,Q;
ll As[100000];
ll Bs[100000];
ll INF=(ll)1000*1000*1000*1000;
ll fastGet() {
  ll ret=0;
  char c=getchar_unlocked();
  // skipping
  while(c<'0' || c > '9') c=getchar_unlocked();
  do {
    ret *= 10;
    ret += (c-'0');
    c = getchar_unlocked();
  } while(c>='0' && c<='9');
  return ret;
}
int main() {
  A=fastGet();
  B=fastGet();
  Q=fastGet();
  REP(i,A)
    As[i]=fastGet();
  REP(i,B)
    Bs[i]=fastGet();
  REP(i,Q) {
    ll x=fastGet();
    ll* ita=lower_bound(As, As+A, x);
    ll* itb=lower_bound(Bs, Bs+B, x);
    ll ans=INF;
    ll alis[2],blis[2];
    alis[0]=ita!=As+A?*ita:INF;
    blis[0]=itb!=Bs+B?*itb:INF;
    alis[1]=ita!=As?ita[-1]:-INF;
    blis[1]=itb!=Bs?itb[-1]:-INF;
    for(ll a:alis)
      for(ll b:blis) {
        ans = min(ans,abs(a-x)+abs(b-a));
        ans = min(ans,abs(b-x)+abs(b-a));
      }
    printf("%lld\n",ans);
  }
  return 0;
}


Measured memory_bytes: 2944
#include <stdio.h>
#include <stdlib.h>
#define NMAX 5000
struct node {
  int id;
  struct node *next;
};
struct node *list[NMAX];
void Insert(int a, int b);
int main(void)
{
  int i, n, m, a, b, top = 0, tail = 0, pcheck = 0, squeue[NMAX], wcount[NMAX] = {0};
  scanf("%d %d", &n, &m);
  for (i = 0; i < n; i++) list[i] = NULL;
  for (i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    Insert(a - 1, b - 1);
    wcount[b-1]++;
  }
  for (i = 0; i < n; i++) if (wcount[i] == 0) squeue[tail++] = i;
  while (top < tail) {
    struct node *nd;
    pcheck |= (tail - top) > 1;
    i = squeue[top++];
    printf("%d\n", i + 1);
    for (nd = list[i]; nd != NULL; nd = nd ->next) {
      if (--wcount[nd->id] == 0) squeue[tail++] = nd->id;
    }
  }
  printf("%d\n", pcheck);
  for (i = 0; i < n; i++) free(list[i]);
}

void Insert(int a, int b)
{
  struct node *p = (struct node*)malloc(sizeof(struct node));
  p->id = b;
  p->next = list[a];
  list[a] = p;
}


Measured memory_bytes: 4924
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
//#define num 1000000007
#define num 998244353
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define inarr(i,a,n,A) for(ll i=a;i<n;i++) { cin>>A[i]; }
#define vll vector<long long>
#define pii pair <int,int>
#define pll pair<long long, long long>
#define vpii vector< pair <int,int>>
#define vpll vector< pair<long long, long long>>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) (a>b)?(a>c)?a:c:(b>c)?b:c
#define min3(a,b,c) (a<b)?(a<c)?a:c:(b<c)?b:c
#define avg(a,b) ((a)+(b))/2
#define push push_back
#define pop pop_back
#define mp make_pair
#define sf int flag=0     //Remember semicolon
#define assmin(a,b) if(b<=a) { a=b; }
#define assmax(a,b) if(b>=a) { a=b; }
#define f first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
typedef long long ll;

ll mod(ll a, ll b)
{
	if(a%b<0)
	{
		return a%b + b;
	}
	return a%b;
}
 
 
ll mod_exp(ll a, ll b, ll c)
{
	ll res=1;
	a=a%c;
	while(b>0)
	{
		if(b%2==1)
		{
			res=(res*a)%c;
		}
		b/=2;
		a=(a*a)%c;
	}
	return res;
}
ll gcd(ll a, ll b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b, a%b);
}
bool prime[3001];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
    prime[1]=false;
    for (int p=2; p*p<=3000; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=3000; i += p) 
                prime[i] = false; 
        } 
    } 
}
ll powe[20];
void power()
{
	powe[0]=1;
	REP(i,1,20)
	{
		powe[i]=(powe[i-1]*10)%num;
        if(powe[i]<0)
        powe[i]+=num;
	}
}
ll A[300005],mx[300005],mn[300005],cur[300005];
void assign(ll n)
{
	REP(i,1,n)
	{
		A[i]=mx[i]=mn[i]=cur[i]=i;
	}
}
double dist(pll p1,pll p2)
{
	return (1.0)*(p1.f-p2.f)*(p1.f-p2.f)+(1.0)*(p1.s-p2.s)*(p1.s-p2.s);
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll n,k;
	cin>>n>>k;
	ll r,p,s;
	cin>>r>>s>>p;
	string str;
	cin>>str;
	ll ans=0;
	REP(i,0,k)
	{
		switch(str[i])
		{
			case 'r':
			ans+=p;
			break;
			case 'p':
			ans+=s;
			break;
			case 's':
			ans+=r;
			break;
		}
	}
	//cout<<ans<<"\n";
	bool taken[n];
	REP(i,0,k)
	{
		taken[i]=true;
	}
	REP(i,k,n)
	{
		if(str[i]!=str[i-k] || !taken[i-k])
		{
			switch(str[i])
			{
				case 'r':
				ans+=p;
				break;
				case 'p':
				ans+=s;
				break;
				case 's':
				ans+=r;
				break;
			}
			taken[i]=true;
		}
		else
		{
			taken[i]=false;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 592
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))

s = input()
t = input()

ans = 0

for i in range(3):
    if s[i] == t[i]:
        ans+=1
print(ans)


Measured memory_bytes: 9064
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>

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

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

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

int main() {
	ll h;
	cin >> h;

	ll cnt = 0;
	ll num = 1;
	while (h > 0) {
		cnt += num;
		h /= 2;
		num *= 2;
	}
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;
const ll INF = 1000000000;

int main() {
    string s; cin >> s;
    int n = s.length();
    vector<int> ans(n, 0);
    int left;
    REP(right,n) {
        int r = 1;
        while(s[right+1]=='R' && right+1<n) {
            right ++;
            r ++;
        }
        int l = 0;
        left = right;
        while (s[left+1]=='L' && left+1<n) {
            left++;
            l++;
        }
        if((r+l)%2==0) {
            ans[right] = (r+l)/2;
            ans[right+1] = (r+l)/2;
        }
        else {
            if(r%2==1) {
                ans[right] = r/2 + 1 + l/2;
                ans[right+1] = r/2 + l/2;
            }
            else {
                ans[right] = r/2 + l/2;
                ans[right+1] = r/2 + l/2 + 1;
            }
        }
        right = left;
    }
    REP(i,n) {
        if(i==n-1) cout << ans[i] << endl;
        else cout << ans[i] << " ";
    }
    return 0;
}

Measured memory_bytes: 1024
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)



def main():
    n = int(ipt())
#    n = 2*10**5
    a = [int(i) for i in ipt().split()]
#    a = [i+1 for i in range(n)]
    way = [[] for i in range(n)]
    for i in range(n-1):
        u,v = map(int,ipt().split())
        u -= 1;v -= 1
        way[u].append(v)
        way[v].append(u)
#    way = [[i-1,i+1] for i in range(n)]
#    way[0] = [1]
#    way[n-1] = [n-2]
    ans = [0]*n
    dp = [10**18]*n
    stk = []

    def solve(ni,pi):
        ai = a[ni]
        pt = bisect.bisect_left(dp,ai)
        stk.append((pt,dp[pt]))
        dp[pt] = ai
        ans[ni] = bisect.bisect_left(dp,10**18-1)
        for i in way[ni]:
            if i == pi:
                continue
            else:
                solve(i,ni)
        pl,val = stk.pop()
        dp[pl] = val
        return None

    solve(0,-1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 381016
fn solve() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let k: usize = sc.read();
    let p: Vec<usize> = sc.vec(n);
    let mut result = 0.0;
    let mut tmp: f64 = 0.0;
    for i in 0..k {
        let a = (p[i] * (p[i] + 1)) as f64 / 2.0;
        let b = p[i] as f64;
        tmp += a / b;
    }
    result = tmp;
    for i in k..n {
        let a = (p[i - k] * (p[i - k] + 1)) as f64 / 2.0;
        let b = p[i - k] as f64;
        tmp -= a / b;
        let a = (p[i] * (p[i] + 1)) as f64 / 2.0;
        let b = p[i] as f64;
        tmp += a / b;
        if result < tmp {
            result = tmp;
        }
    }
    println!("{:.15}", result);
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| solve())
        .unwrap()
        .join()
        .unwrap();
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

using namespace std;

bool check(vector<int> line){
		if(line[0]!=1)return false;
		for(auto &i:line)if(!i)return false;
		return true;
}

int func(string str){
	int res = 0;
	int sum = 0;
	for(int l = 0;l<str.size();++l){
			if(sum==0){
					vector<int> cnt(4,0);
					int dir = 0;
					int sum2 = 0;
					bool used = false;
					for(int p = l;p<str.size();++p){
							if(str[p]=='L'){
									dir = (dir + 3) % 4;
									--sum2;
							}else{
									dir = (dir+1) % 4;
									used = true;
									++sum2;
							}
							if(used)++cnt[dir];
							if(dir==0){
									if(sum2!=4)break;
									if(check(cnt))++res;
									break;
							}
					}
			}
			if(str[l]=='L'){
					sum = (sum+3)%4;
			}else{
					sum = (sum+1)%4;
			}
	}
	return res;
}

int main(){
	string str;
	cin >> str;
	cout << func(str) << endl;
	return 0;
}



Measured memory_bytes: 3220
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<random>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    int w = 0;
    ll ans = 0;
    for(int i = s.size(); i >= 0; i--){
        if(s[i] == 'W'){
            w++;
        }else{
            ans += w;
        }
    }
    cout << ans << '\n';
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    ll N;
    cin >> N;

    ll res = 0;
    if(N%2==1){
    	res = 0;
    }else{
    	ll x=0, y=0;
    	ll M = N;
    	while(M>0){
    		x += M/2;
    		M /= 2;
    	}
    	//dump(x)

    	M = N/2;
    	while(M>0){
    		y += M/5;
    		M /= 5;
    	}
    	//dump(y);

    	res = min(x, y);
    }
    cout << res << endl;
    return 0;
}

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

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;

int main() {
	int N; cin >> N;
	vector<int> Nr;
	for(int i=0; i<N; i++) {
		int x; scanf("%d", &x);
		Nr.push_back(x);
	}
	int ans = INF;
	for(int v=-100; v<=100; v++) {
		int now = 0;
		for(int i=0; i<N; i++) {
			now += (v-Nr[i]) * (v-Nr[i]);
		}
		if(now < ans) ans = now;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <utility>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <iterator>
#include <random>
#include <fstream>
#include <chrono>
#include <math.h>
#include <cctype>
using namespace std;
#define int long long
#define forn(i, n) for (int i = 0; i < n; ++i)

const int mod = 1e9 + 7;
int32_t main() {
    ios::sync_with_stdio(false);
    // dp по маске у нас 10110111110
    //                     10010110100
    //                  dp[00100001010]
    int n;
    cin >> n;
    vector<vector<int>> a(n + 3, vector<int> (n + 3, 0));
    forn(i, n){
        forn(j,n){
            cin >> a[i][j];
        }
    }
    vector<int>score((1 << n) + 33, 0);
    for(int mask = 0; mask < (1 << n); mask++) {
        for(int i = 0; i < n; i++){
            if((1 << i) & mask) {
                for (int j = 0; j < i; j++) {
                    if((1 << j) & mask)
                        score[mask] += a[i][j];
                }
            }
        }
    }
    vector<int> dp((1<< n) +33, 0);
    int ans = 0;
    for(int mask =  1; mask < (1 << n); mask++){
        for (int submask = mask; submask > 0; submask--, submask &= mask) {
            dp[mask] = max(dp[mask], score[submask] + dp[mask ^ submask]);
        }
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}


Measured memory_bytes: 4300
#include <stdio.h>
int main()
{
    int cm[5];
    int end;
    int k = 0, sum = 0;
    for (int i = 0; i < 5; i++)
        scanf("%d", &cm[i]);
    end = cm[0];
    for (int i = 1; i < 5; i++)
    {
        if ((cm[i] + 9) % 10 < (end + 9) % 10)
        {
            end = cm[i];
            k = i;
        }
    }
    for (int i = 0; i < 5; i++)
    {
        if (i == k)
            sum += cm[i];
        else
            sum += cm[i] + 9 - (cm[i] + 9) % 10;
    }
    printf("%d", sum);
    return 0;
}

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

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

    int adj_matrix[101][101] = {0};
    int visit[101] = {0};
    queue<int> q;
    int dist_from_start[101] = {0};
    for (int i = 1; i <= n; i++)
    {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; j++)
        {
            int x;
            cin >> x;
            adj_matrix[u][x] = 1;
        }
    }

    q.push(1);
    visit[1] = 1;
    while (!q.empty())
    {
        int now = q.front();
        for (int i = 1; i <= n; i++)
        {
            if (adj_matrix[now][i] == 1 && visit[i] == 0)
            {
                visit[i] = 1;
                q.push(i);
                dist_from_start[i] = dist_from_start[now] + 1;
            }
        }
        q.pop();
    }

    for (int i = 1; i <= n; i++)
    {
        if (i == 1 || dist_from_start[i] > 0)
        {
            cout << i << " " << dist_from_start[i] << endl;
        }
        else
        {
            cout << i << " " << -1 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3132
using System;
using System.Collections.Generic;

namespace ABC042_B_Iroha_Loves_Strings
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			string[] input = Console.ReadLine().Split(' ');
			int n = int.Parse(input[0]);
			int l = int.Parse(input[1]);
			
			List<string> Strs = new List<string>();

			for (int i = 0; i < n; i++) {
				Strs.Add(Console.ReadLine());
			}
			
			Strs.Sort();

			for (int i = 0; i < n; i++) {
				Console.Write(Strs[i]);
			}
		}
	}
}

Measured memory_bytes: 13408
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

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

  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &x: a) cin >> x;

  int ans = 0;
  for (int i = 0; i < n-1; i++) {
    if (a[i] < a[i+1]) ans++;
  }

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3280
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
counter = [0]*(maxA+1)
for ai in A:
    for m in range(ai, maxA+1, ai):
        counter[m] += 1
ans = 0
for ai in A:
    ans += (counter[ai] == 1)
print(ans)


Measured memory_bytes: 32332
#include <stdio.h>
#define MAX 123456

bool p[2*MAX+1];

void prime(){
int i,j;
for(i=0; i <= 2*MAX; i++) p[i] = 1;
for(i=2; i<= MAX; i++){
if(p[i] == 0) continue;
j = i+i;
while(j <= 2*MAX){
p[j] = 0;
j += i;
}
}
}

int main(){
int n,cnt,i;

prime();
while(1){
scanf("%d", &n);
if(n == 0) break;
cnt = 0;
for(i=n+1; i <= 2*n; i++)
cnt += p[i];
printf("%d\n",cnt);
}
}

Measured memory_bytes: 1268
N,K = map(int,input().split())

def get_expectation (x):
    return (float(x)+1)/2
exp = list(map(get_expectation,input().split()))


total = sum(exp[0:K])
maxim = total
for i in range(K,N):
    total -= exp[i-K]
    total += exp[i]
   
    
    if maxim <= total:
        maxim = total

print("%.10f" % maxim)

Measured memory_bytes: 23524
while True:
    H, W = map(int, input().split())
    if H == 0 and W == 0:
        break
    for i in range(H):
        if i == 0 or i == H - 1:
            print("#"*W, end="")
        else:
            for j in range(W):
                if j == 0 or j == W - 1:
                    print("#", end="")
                else:
                    print(".", end="")
        print()
    print()



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

class pow10calculater{
    public:
    long long product[100020];

    pow10calculater(){
        product[0] = 1;
        for( int i = 1; i < 100020; i++ ){
            product[i] = (10 * product[i-1]) % 13;
        }
    }

    long long get(int i){
        return product[i];
    }
};

int main(){
    // 10のi乗を13で割ったあまりを計算するクラス　.get(i)で呼び出す
    pow10calculater pow10;
    //　入力　→　vector<int>に入れなおす作業（'?'は１５になる）
    string s; cin >> s;
    int N = s.size();
    vector<int> S(N);
    for( int i = 0; i < N; i++ ){
        int k = s[N-i-1] - 48;
        S[i] = k;
    }

    int question = '?' - 48;//'?' - 48 == 15
    long long MOD = 1000000007LL;
    //動的計画法　dp[ここまでに見つかった解][１３で割ったあまり]　答えはdp[N-1][5]
    vector<vector<long long>> dp(N,vector<long long>(13,0LL));
    for( int i = 0; i < N; i++ ){

        if( i == 0 ){
            if( S[i] != question ){
                dp[0][S[i]] = 1LL;
            } else {
                for( int j = 0; j < 10; j++ ){
                    dp[0][j] = 1LL;
                }
            }
        } else {
            if( S[i] != question ){
                for( int j = 0; j < 13; j++ ){
                    dp[i][(j+S[i]*pow10.get(i)) % 13] = dp[i-1][j];
                }
            } else {
                for( int j = 0; j < 13; j++ ){
                    for( int k = 0; k < 10; k++ ){
                        dp[i][(j + k*pow10.get(i)) % 13] += dp[i-1][j];
                        dp[i][(j + k*pow10.get(i)) % 13] %= MOD;
                    }
                }
            }
        }

    }


    cout << dp[N-1][5] << endl;   
}

Measured memory_bytes: 14848
#include<stdio.h>
#define MAX 8
#define FREE -1
#define NOT_FREE 1

int Board[MAX][MAX], row[MAX], col[MAX], dpos[2*MAX-1], dneg[2*MAX-1];

void initialize() {
    for (int i=0; i<MAX; i++) row[i]=col[i]=FREE;
    for (int i=0; i<2*MAX-1; i++) dpos[i]=dneg[i]=FREE;
}

void printBoard() {
    for (int i=0; i<MAX; i++) {
        for (int j=0; j<MAX; j++) {
            if (row[i]!=j) printf(".");
            else printf("Q");
        }
        printf("\n");
    }
}

void recursive(int i) {
    if (i>=MAX) {
        printBoard();
        return;
    }
    else if (row[i]==FREE) {
        for (int j=0; j<MAX; j++) {
            if (row[i]!=FREE || col[j]!=FREE || dpos[i+j]!=FREE || dneg[i-j+MAX-1]!=FREE) continue;
            else {
                row[i]=j;
                col[j]=dpos[i+j]=dneg[i-j+MAX-1]=NOT_FREE;
                recursive(i+1);
                row[i]=FREE;
                col[j]=dpos[i+j]=dneg[i-j+MAX-1]=FREE;
            }
        }
    }
    else recursive(i+1);
}

int main() {
    int n, r, c;

    initialize();

    scanf("%d", &n);

    for (int i=0; i<n; i++) {
        scanf("%d %d", &r, &c);
        row[r] = c;
        col[c] = dpos[r+c] = dneg[r-c+MAX-1]=NOT_FREE;
    }

    recursive(0);
    return 0;
}


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

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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    string s;
    int k;
    cin >> s >> k;
    ll ans = 0;
    if(s.size() == 1) {
        cout << (ll)s.size() * k / 2 << "\n";
        return 0;
    }

    if(s[0] != s[s.size()-1]){
        for(int i = 1; i <= s.size()-1; ++i){
            if(s[i] == s[i-1]) {
                ans += k;
                s[i] = 'A';
            }
        }
        cout << ans << "\n";
        return 0;
    }

    string t = s + s;
    int cnt = 0;
    for(int i = 1; i <= t.size()-1; ++i){
        if(t[i] == t[i-1]) {
            t[i] = 'A';
            ++cnt;
        }
    }
    if(t[0] != t[t.size()-1]) {
        ans = (ll)cnt * (k / 2);
        if(k % 2) {
            for(int i = 0; i < s.size(); ++i){
                if(t[i] == 'A') ++ans;
            }
        }
        cout << ans << "\n";
        return 0;
    }

    int cnt2 = 0;
    cnt = 0;
    for(int i = 0; i < s.size(); ++i){
        if(t[i] == 'A') ++cnt;
    }
    for(int i = s.size(); i < t.size(); ++i){
        if(t[i] == 'A') ++cnt2;
    }
    cout << cnt + (ll)cnt2 * (k-1) << "\n";
    return 0;
}

Measured memory_bytes: 256