akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, Y) for (int(X) = 0; (X) < (Y); ++(X))
#define rrep(X, Y) for (int(X) = (Y)-1; (X) >= 0; --(X))
#define itrep(X, Y) for (auto(X) = (Y).begin(); (X) != (Y).end(); (X)++)
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

ll helper(ll n, vl a, bool isPos) {
  ll ret = 0;
  ll sum = 0;
  for (ll i = 0; i < n; i++) {
    ll sumTmp = sum + a[i];
    if (isPos) {
      if (sumTmp >= 0) {
        ret += sumTmp + 1;
        sum = -1;
      } else {
        sum = sumTmp;
      }
      isPos = false;
    } else {
      if (sumTmp <= 0) {
        ret += 1 - sumTmp;
        sum = 1;
      } else {
        sum = sumTmp;
      }
      isPos = true;
    }
  }
  return ret;
}

void solve(long long n, std::vector<long long> a) {
  ll ret1 = helper(n, a, true);
  ll ret2 = helper(n, a, false);
  ll ans = min(ret1, ret2);
  print(ans);
}

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


Measured memory_bytes: 1804
n,a,b = map(int, input().split())

def s(sum,a,b):
    t = 0
    if sum >= a and sum <= b:
        t = 1
    return t

def S(i):
    sum = 0
    while i > 0:
        sum += i%10
        i = int(i/10)
    return sum

num = 0
for i in range(1,n+1):
    sum = S(i)
    if s(sum,a,b) == 1:
        num += i
print(num)


Measured memory_bytes: 9192
n=int(input())
s=input()
t=input()
mod=10**9+7

l=[]
k=0
i=0
while i<n:
    if s[i]==t[i]:
        if k==0:
            l.append(3)
        elif k==1:
            l.append(2)
        else:
            l.append(1)
        k=1
        i+=1
    else:
        if k==0:
            l=l+[3,2]
        elif k==1:
            l=l+[2,1]
        else:
            l=l+[3,1]
        k=2
        i+=2
ans=1
for i in range(n):
    ans*=l[i]
print(ans%mod)

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

using namespace std;
using ll = long long;

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

  int h, w;
  cin >> h >> w;
  int ch, cw;
  int dh, dw;
  cin >> ch >> cw;
  cin >> dh >> dw;
  ch--;
  cw--;
  dh--;
  dw--;
  vector<vector<char>> s(h, vector<char>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> s[i][j];
    }
  }

  auto check = [&](int x, int y) {
    if (x < 0 || x >= w || y < 0 || y >= h)
      return false;
    if (s[y][x] == '#')
      return false;
    return true;
  };

  queue<tuple<int, int>> q;
  int d = 0;
  q.push({cw, ch});
  vector<vector<bool>> visit(h, vector<bool>(w, false));
  while (true) {
    vector<pair<int, int>> v;
    while (!q.empty()) {
      auto [x, y] = q.front();
      q.pop();
      if (visit[y][x])
        continue;
      visit[y][x] = true;
      v.push_back({x, y});
      if (x == dw && y == dh) {
        cout << d << endl;
        return 0;
      }

      if (check(x + 1, y))
        q.push({x + 1, y});
      if (check(x - 1, y))
        q.push({x - 1, y});
      if (check(x, y + 1))
        q.push({x, y + 1});
      if (check(x, y - 1))
        q.push({x, y - 1});
    }
    for (auto [x, y] : v) {
      for (int dy = -2; dy <= 2; dy++) {
        for (int dx = -2; dx <= 2; dx++) {
          if (dx == 0 && dy == 0)
            continue;
          if (dx == 1 && dy == 0)
            continue;
          if (dx == -1 && dy == 0)
            continue;
          if (dx == 0 && dy == 1)
            continue;
          if (dx == 0 && dy == -1)
            continue;
          int nx = x + dx;
          int ny = y + dy;
          if (!check(nx, ny))
            continue;
          if (visit[ny][nx])
            continue;
          q.push({nx, ny});
        }
      }
    }
    d++;
    if (q.empty())
      break;
  }

  cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 4980
#include <iostream>
#include <limits>
#include <algorithm>


int main() {
	int N;
	std::cin >> N;
	int h[N];
	for (int i = 0; i < N; ++i) {
		std::cin >> h[i];
	}
	
	int dp[N];
	for (int i = 0; i < N; ++i) {
		dp[i] = std::numeric_limits<int>::max();
	}
	dp[0] = 0;
	dp[1] = abs(h[0] - h[1]);
	for (int i = 2; i < N; ++i) {
		dp[i] = std::min(dp[i - 1] + std::abs(h[i] - h[i - 1]), dp[i - 2] + std::abs(h[i] - h[i - 2]));
	}
	std::cout << dp[N - 1];
	
	return 0;	
}


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

int main () {
	ios_base::sync_with_stdio(false);cin.tie (nullptr);cout.tie(nullptr);
	int n,m;
	cin>>n>>m;
	int x;
	vector<int> v;
	while(m--){
		cin>>x;
		v.push_back(x);
	}
	auto j=v.end(),i=v.begin();
	v.push_back(*i);
	int ma=0;
	for (; i <j ; ++i) {
		int t=abs(*(i+1)-*i);
		if(t>n/2)t=n-t;
		ma=ma>t?ma:t;
	}
	cout<<n-ma;
	return 0;
}

Measured memory_bytes: 1400
import java.util.Scanner;

public class Main {

	public static void main (String[] args)  {

		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		int z = sc.nextInt();
		int w = sc.nextInt();
		
		if (x==z) {
			System.out.println("0");
		} else {
			System.out.println("1");
		}

	}

}


Measured memory_bytes: 21840
import java.util.Scanner;

public class Main {
  public static void main (String[] args) {
    Scanner in = new Scanner(System.in);

    while (in.hasNext()) {
      int N = in.nextInt();
      int[] H = new int[N];

      for (int i = 0; i < H.length; ++i) {
        H[i] = in.nextInt();
      }

      int max = 0;
      int count = 0;
      for (int i = 1; i < H.length; ++i) {
        if (H[i] <= H[i - 1]) {
          ++count;
        } else {
          max = Math.max(max, count);
          count = 0;
        }
      }
      max = Math.max(max, count);

      System.out.println(max);
    }
  }
}

Measured memory_bytes: 50008
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#define int long 
using namespace std;

signed main() {
	int N,K;
	cin >> N >> K;
	vector<int> vec(N);
	for(int i = 0;i < N;i++) {
		cin >> vec.at(i);
	}
	sort(vec.begin(),vec.end());
	int answer = 1e10;
	for(int i = 0;i < N - K + 1;i++) {
		answer = min(answer,vec.at(i + K - 1) - vec.at(i));
	}
	cout << answer << endl;
}

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

const int INF = 1000000;
int dp[100000][3][3][2];
int col[10] = {-1, 0, 1, 2, 0, -1, 2, 0, 1, 2};

void init(int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                for (int l = 0; l < 2; ++l) { dp[i][j][k][l] = INF; }
            }
        }
    }
}

int main() {
    string seq;
    while (cin >> seq) {
        if (seq == "#") break;
        int n = seq.size();
        init(n);
        int col_0 = col[seq[0] - '0'];
        for (int le = 0; le < 3; ++le) {
            for (int ri = le; ri < 3; ++ri) {
                if (le == col_0) { dp[0][le][ri][0] = 0; }
                if (ri == col_0) { dp[0][le][ri][1] = 0; }
            }
        }
        for (int i = 0; i < n - 1; ++i) {
            for (int le = 0; le < 3; ++le) {
                for (int ri = le; ri < 3; ++ri) {
                    int nxt = col[seq[i + 1] - '0'];
                    if (nxt <= ri) {
                        dp[i + 1][nxt][ri][0] = min(dp[i + 1][nxt][ri][0], dp[i][le][ri][0] + 1);
                        dp[i + 1][nxt][ri][0] = min(dp[i + 1][nxt][ri][0], dp[i][le][ri][1]);
                    }
                    if (le <= nxt) {
                        dp[i + 1][le][nxt][1] = min(dp[i + 1][le][nxt][1], dp[i][le][ri][0]);
                        dp[i + 1][le][nxt][1] = min(dp[i + 1][le][nxt][1], dp[i][le][ri][1] + 1);
                    }
                }
            }
        }
        int mn = INF;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                for (int k = 0; k < 2; ++k) { mn = min(mn, dp[n - 1][i][j][k]); }
            }
        }
        cout << mn << endl;
    }
    return 0;
}


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

int main(void) {
  int a,b,x;
  scanf("%d %d %d",&a,&b,&x);
  
  //満杯に近い
  if(x>a*a*b/2)
  {
	printf("%.10f",atan((2.0*b-2.0*x/a/a)/a)/3.14159265358979*180);
  }else{
  	printf("%.10f",atan(a*b*b/2.0/x)/3.14159265358979*180);
  }
}

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

int main(){
  typedef unsigned long long _ull;
  const _ull LIM = 1000000000000000000ULL;
  int N;

  cin >> N;
  vector<_ull> A(N);

  for(int i = 0; i < N; i++){
    cin >> A.at(i);
    if(A.at(i) == 0) {
      cout << 0 << endl;
      return 0;
    }
  }

  _ull mul = 1ULL;
  
  for(int i = 0; i < N; i++){
    if(LIM/A.at(i) < mul) {
      cout << -1 << endl;
      return 0;
    }
    mul *= A.at(i);
    if(mul > LIM){
      cout << -1 << endl;
      return 0;
    }
  }
  cout << mul << endl;
  return 0;  
}


Measured memory_bytes: 4056
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod107 1000000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(), v.end()
#define PI acos(-1)

const ll INF = 10010001010;
const int inf = 1000034000;
typedef vector<ll> vecl;
typedef vector<int> veci;
typedef tuple<string, int, int> TUP;

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout << fixed << setprecision(15);
    int A, B;
    cin >> A >> B;
    cout << (A + B) % 24 << endl;
}


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

#define ll long long
#define all(x) (x).begin(), (x).end()
const long long INF = 1LL << 60;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // cout << fixed << setprecision(5);

    // 入力
    int n, k;
    cin >> n >> k;

    int ans      = 0;
    int ball_max = 0;
    int tmp      = 0;

    // 処理
    if (k == 1) {
        ans = 0;
    } else if (k >= 2) {
        ball_max = n - (k - 1);
        ans      = ball_max - 1;
    }

    // 出力
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define maxn 2000+40
#define mod 1000000007
typedef long long int LL;
int n , m;
LL dp[maxn][maxn];
int a[maxn];
int b[maxn];
int main()
{
 
     cin >> n >> m ;
        memset(dp,0,sizeof(dp));
        for(int i = 1 ; i <= n ; ++i)
        {
            scanf("%d ",&a[i]);
        }
        for(int i = 1 ; i <= m ; ++i)
        {
            scanf("%d",&b[i]);
        }
        for(int i = 1 ; i <= n ; ++i)
        {
            for(int j = 1 ; j <= m ; ++j)
            {
                if( a[i] == b[j] )
                {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1;
                }
                else dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
                dp[i][j] %= mod;
            }
        }
        cout << (dp[n][m] + mod+1)%mod << endl;
}

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

int const N = 20, M = 190, md = 1e9 + 7;
pair<int, int> dp[1 << N - 1];
int edm[M], nn[M + 2][M + 2], fr[1 << N - 1];
vector<pair<int, int> > tr[N + 1];

inline void ad(int &x, int y) { if ((x += y) >= md)x -= md; }
inline int bc(int x){
	int an = 0;
	while (x){
		++an;
		x ^= x & -x;
	}
	return an;
}

int ta;
int go(int v, int p = 0){
	if (v == ta)return 0;
	f(i, 0, tr[v].size()){
		int u = tr[v][i].first, id = tr[v][i].second;
		if (u == p)continue;
		int t = go(u, v);
		if (t == -1)continue;
		return t | 1 << id;
	}
	return -1;
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	f(i, 1, m + 2){
		nn[i][i] = i;
		f(j, i + 1, m + 2)nn[i][j] = (ll)nn[i][j - 1] * j % md;
	}
	f(i, 0, m){
		int a, b;
		scanf("%d%d", &a, &b);
		if (i < n - 1){
			tr[a].push_back(make_pair(b, i));
			tr[b].push_back(make_pair(a, i));
		}else {
			ta = b;
			edm[i] = go(a);
		}
	}
	f(i, n - 1, m)f(j, 0, 1 << n - 1)if (j & edm[i])++fr[j];
	dp[0] = make_pair(1, 0);
	f(i, 0, 1 << n - 1)f(j, 0, n - 1)if (!(i >> j & 1)){
		int b = bc(i), n = b + fr[i], c = dp[i].first, s = dp[i].second, ni = i | 1 << j, k = fr[ni] - fr[i];
		if (k){
			c = (ll)c * nn[n + 1][n + k] % md;
			s = (ll)s * nn[n + 2][n + 1 + k] % md;
		}
		ad(s, (ll)(b + 1) * c % md);
		ad(dp[ni].first, c);
		ad(dp[ni].second, s);
	}
	printf("%d\n", dp[(1 << n - 1) - 1].second);
}

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

int main() {
	int a, b, c, x; cin >> a >> b >> c >> x;
	
	int ans = 0;
	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			for (int k = 0; k <= c; k++) {
				if (x == i * 500 + j * 100 + k * 50) {
					ans++;
				}
			}
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long min = Long.MAX_VALUE;
        long sum = 0;
        for(int i = 0; i<5; i++) {
            min = Math.min(sc.nextLong(), min);
        }
        sum = (long)Math.ceil((double)N/(double)min) + 4;
        System.out.println(sum);
    }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
int n;
char str[128];

void solve(){
    cin>>str;
    int fld=0;
    int pnt[10]={0};
    for(int i=0;i<100;i++){
        int p=i%n;
        if(str[i]=='M')pnt[p]++;
        else if(str[i]=='S'){
            fld+=pnt[p]+1;
            pnt[p]=0;
        }
        else{
            pnt[p]+=fld+1;
            fld=0;
        }
    }
    sort(pnt,pnt+n);
    for(int i=0;i<n;i++)cout<<pnt[i]<<" ";
    cout<<fld<<endl;
}

int main(){
    while(cin>>n,n)solve();
    return 0;
}

Measured memory_bytes: 1184
#include<iostream>
using namespace std;
#include<string>
#include<utility>
#include<algorithm>

int main(){
    int N;
    cin >> N;
    int A[N];
    for(int i=0;i<N;++i){
        cin >> A[i];
    }
    pair<int,int> num[N];
    for(int i=0;i<N;++i){
        num[i]=make_pair(A[i],i);
    }
    sort(num,num+N);
    for(int i=0;i<N;++i){
        cout << num[i].second+1 <<endl;
    }
}

Measured memory_bytes: 2048
R, L, K = map(int, input().split())
V = [[0]*R for _ in range(L)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[c-1][r-1] = v
A, B, C, D = [[0]*(R+1) for _ in range(4)]
for i in range(L):
    for j in range(R):
        A[j] = max(A[j-1], B[j-1], C[j-1], D[j-1])
        v = V[i][j]
        if v != 0:
            D[j], C[j], B[j] = max(C[j] + v, D[j]), max(B[j] + v, C[j]), max(A[j] + v, B[j])

print(max(A[-2], B[-2], C[-2], D[-2]))

Measured memory_bytes: 147084
n,k = map(int, input().split()) #右の要素に対して左の関数を適応する
a = list(map(int, input().strip().split())) #strip()は文字列の両端の空白や改行を削除する

for i in range(len(a)):
    a[i] -= 1 #入力値を添字に合わせる

visited = [-1] * n #[-1. -1. -1. …]を定義
now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
r = 1
while i <= k:
    next = a[now] #次に移動する場所
    if visited[next] >= 0:
        r = i-visited[next] #途中から繰り返される場合もあるのでそこまでにかかった回数を引いている
        pre_roop = visited[next] #ループしない部分の回数を代入
        pos = next #ループが始まる場所を代入
        break #同じ場所に帰ってきたらfor文を抜け出す
    else:
        visited[next] = i
        now = next
        i += 1

if i > k:
    print(now + 1) #今いる場所を出力
else:
    l = (k - pre_roop) % r
    i = 0
    p = pos #ループが開始される部分からスタート
    for _ in range(l):
        p = a[p]
        i +=1

    print(p+1)

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

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using pint = pair<int, int>; 
using pll  = pair<ll, ll>;
using vint = vector<int>; 
using vll  = vector<ll>;
using vstr = vector<string>;

//　定数, 変数 *********************************************
const ll MOD=1e9+7;
const ll INF=1ll<<60;

ll N;

map<ll,ll> mp;
vector<pair<ll,ll>> fs;
//***********************************************************
void dp(ll n)
{
    // 割る数の初期値
    ll a = 2;
    // √n ≧ a ( n ≧ a * a ) の間ループ処理
    while (n >= a * a) {
        // a で割り切れたら、a は素因数
        // そして、割られる数を a で割る
        // a で割り切れなかったら、 a を 1 増加させる
        if (n % a == 0) {
            //printf("%d * ", a);
            ++mp[a];
            n /= a;
        } else {
            ++a;
        }
    }
    // 最後に残った n は素因数
    //printf("%d\n", n);
    ++mp[n];
}


// *********************************************************


void dp2(ll n){
    for(ll i=2; i*i<=n; ++i){
        int x=0;
        while(n%i == 0){
            n /= i;
            ++x;
        }
        if(x != 0){
            fs.emplace_back(i,x);
        }
    }
    if(n != 1){
        fs.emplace_back(n,1);
    }
}
// *****************************************************


int main(){
    int sum = 0;
    cin >> N;
    
    if (N==1){
        cout << 0 << endl;
        return 0;
    }

    dp(N);
    
    for(auto i=mp.begin(); i != mp.end(); ++i){
        int x = i->second;
        int b = 1;
        while(b <= x){
            x -= b;
            ++b;
            ++sum;
        }

    }    
    


    cout << sum << endl;
    
    return 0;
}

Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int count = 0;

		for(int i = 0; i < n; i++) {
			if(sc.nextInt() >= k) count++;
		}

		System.out.println(count);

		sc.close();

	}

}

Measured memory_bytes: 48592
#include<iostream>
using namespace std;
int n;
char arr[100000];
char brr[100000];
int pd(char a,char b)
{
	brr[0]=a;
	brr[1]=b;
	for(int i=1;i<n-1;i++)
	{
		if(brr[i]=='S'&&arr[i]=='o'||brr[i]=='W'&&arr[i]=='x')
		{
			brr[i+1]=brr[i-1];
		}
		else
		{
			if(brr[i-1]=='S')
			{
				brr[i+1]='W';
			}
			else
			{
				brr[i+1]='S';
			}
		}
	}
	char t;
	if(brr[n-1]=='S'&&arr[n-1]=='o'||brr[n-1]=='W'&&arr[n-1]=='x')
	{
		t=brr[n-2];
	}
	else
	{
		if(brr[n-2]=='S')
		{
			t='W';
		}
		else
		{
			t='S';
		}
	}
	if(t==brr[0])
	{
		if(brr[0]=='S'&&arr[0]=='o'||brr[0]=='W'&&arr[0]=='x')
		{
			if(brr[1]==brr[n-1])
			{
				for(int i=0;i<n;i++)
				{
					cout<<brr[i];
				}
				return 0;
			}
		}
		else
		{
			if(brr[1]!=brr[n-1])
			{
				for(int i=0;i<n;i++)
				{
					cout<<brr[i];
				}
				return 0;
			}
		}
	}
	return 1;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	char crr[4][2]={'W','W','W','S','S','S','S','W'};
	for(int i=0;i<4;i++)
	{
		if(pd(crr[i][0],crr[i][1])==0)
			return 0;
	}
	cout<<-1;
}

Measured memory_bytes: 512
n = int(input())
x = [0]*n
y = [0]*n
for i in range(n-1, -1, -1):
  a,b = map(int, input().split())
  x[i] = a
  y[i] = b

ans = 0
for i in range(n):
  if (x[i]+ans) % y[i] != 0:
    ans += y[i]-(x[i]+ans)%y[i]
print(ans)

Measured memory_bytes: 16648
S_hint=input()
T=input()
List_S_hint=list(S_hint)
S_candidates=[]
Out=0
for i in range(len(S_hint)-len(T)+1):
  Out=0
  Word=""
  Candidate=list(List_S_hint)
  for j in range(len(T)):
    if Candidate[i+j] is "?":
      Candidate[i+j]=T[j]
    elif Candidate[i+j]==T[j]:
      pass
    else:
      Out=1
      break
  if Out==1:
    pass
  else:
    for n in Candidate:
      if n=="?":
        Word+="a"
      else:
        Word+=n
    S_candidates.append(Word)  
if len(S_candidates)==0:
  print("UNRESTORABLE")
else:  
  print(min(S_candidates))      
      
      

Measured memory_bytes: 3064
import sys


def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))


def frog_1(arr, n, k):

    dp = [0] * (n + 1)
    dp[1] = 0

    for i in range(2, n+1):
        dp[i] = float("inf")
        for j in range(1, k+1):
            if i - j >= 1:
                dp[i] = min(dp[i], dp[i - j] + abs(arr[i - 1] - arr[i - j - 1]))

    return dp[n]


def vacation(mat, n):

    for i in range(1, n+1):
        for j in range(3):
            x = mat[i][j]
            for t in range(3):
                if t != j:
                    mat[i][j] = max(mat[i][j], mat[i - 1][t] + x)


    return max(mat[n])



# n, k = get_ints()
# arr = get_array()

# sys.stdout.write(str(frog_1(arr, n, k)))

n = int(sys.stdin.readline())
mat = [[0 for i in range(3)]]

for i in range(n):
    mat.append(list(map(int, sys.stdin.readline().strip().split())))

sys.stdout.write(str(vacation(mat, n)))



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

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n), b(m), c, d;
	for (int& i : a) cin >> i;
	for (int& i : b) cin >> i;
	set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.end()));
	set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(d, d.end()));
	cout << c.size() << ' ' << d.size() << endl;
	for (int& i : c) cout << i << endl;
	for (int& i : d) cout << i << endl;
}


Measured memory_bytes: 4948
nn=int(input())
s_list=[]
for i in range(nn):
	s_list.append(str(input()))
mm=int(input())
t_list=[]
for j in range(mm):
	t_list.append(str(input()))

count_list=[]
for k in range(nn):
	name = s_list[k]
	count=0
	for l in range(nn):
		if name==s_list[l]:
			count+=1
	for m in range(mm):
		if name==t_list[m]:
			count-=1
	count_list.append(count)

max_value=max(count_list)
if max_value<=0:
	max_value=0
print(max_value)


Measured memory_bytes: 3064
#13
a,b,c = map(int,input().split())
cnt = 0
if a%2 == 1 or b%2 == 1 or c%2 == 1:
    print('0')

elif a==b==c and a%2==0:
            print('-1')
    
elif not a==b==c:
    while a%2 == b%2 == c%2 == 0:
        a,b,c = b//2+c//2,c//2+a//2,a//2+b//2
        cnt+=1
    print(cnt)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int row,col;
bool f[444][444];
int vis[444][444];
int B[444*444],W[444*444],T;
void dfs(int x,int y,bool c){
	if(x < 0 || x >= row || y < 0 || y >= col)return;
	if(f[x][y] != c || vis[x][y] != -1)return;
	vis[x][y] = T;
	bool cc = c;
	if((x+y)%2)cc = !cc;
	if(!cc)W[T] ++;
	dfs(x-1, y, c);
	dfs(x+1, y, c);
	dfs(x, y-1, c);
	dfs(x, y+1, c);
}
int main(){
	char s[999];
	scanf("%d%d",&row,&col);
	for(int i=0; i<row; i++){
		scanf("%s",s);
		for(int j=0; j<col; j++)
			f[i][j] = (s[j] == '#');
	}
	for(int i=0; i<row; i++)for(int j=0; j<col; j++)
		if((i+j)%2)f[i][j] = !f[i][j];
	memset(vis,-1,sizeof(vis));
	for(int i=0; i<row; i++)for(int j=0; j<col; j++){
		if(vis[i][j] == -1){
			dfs(i,j,f[i][j]);
			T++;
		}
	}
	long long int res = 0;
	for(int i=0; i<row; i++)for(int j=0; j<col; j++)
		if((i+j)%2)f[i][j] = !f[i][j];
	for(int i=0; i<row; i++)for(int j=0; j<col; j++)if(f[i][j])
		res += W[vis[i][j]];
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 6144
n = int(input())
a = input().split()
a = [int(m) for m in a]
pn = [0]*n
for i in range(n):
    pn[(-a[i] + n - 1)//2] += 1
    if (-a[i] + n - 1)//2 != (a[i] + n - 1)//2:
        pn[(a[i] + n - 1)//2] += 1
for i in range(n):
    if pn[i] > 2:
        print(0)
        exit()
    if n % 2 != 0:
        if pn[(n - 1) // 2] > 1:
            print(0)
            exit()

ans = 1
mod = 10**9 + 7
for i in range(n):
    if i <= (n - 1) // 2:
        ans = (ans * pn[i]) % mod
    else:
        break
print(ans)

Measured memory_bytes: 13880
#include <bits/stdc++.h>
#define ll long long int
#define fr(i, a, b) for (ll i = a; i < b; i++)
#define pb(v, a) v.push_back(a)
#define Sort(v) sort(v.begin(), v.end())
#define For(m) for (auto it = m.begin(); it != m.end(); it++)
#define mod 1000000007
using namespace std;



int main()
{
    ll arr[4];
 fr(i,0,4)cin >> arr[i];
 sort(arr,arr+4);
 bool res = true;
 if(arr[0]!=1||arr[1]!=4||arr[2]!=7||arr[3]!=9)res=false;
 if(res)
 {
     cout << "YES";
 }
 else 
  cout << "NO";

  return 0;
}


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

#define REP(i, a, b) for ( int i = (a); i < (b); i++ )

using namespace std;

int a;
char s[5005];

int main(void) {
	scanf("%d", &a);
	scanf("%s", s);

	string str(s);

	if (a >= 3200) printf("%s\n", s);
	else printf("red\n");

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) cout << fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

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

	ll n, k;
	cin >> n >> k;
	vll v(n);
	for (ll i = 0; i < n; i++) cin >> v[i];

	ll ans = 0;
	for (ll i = 0; i <= n; i++) {
		for (ll j = i; j <= n; j++) {
			if (i + n - j > k) continue;
			ll sum = 0;
			priority_queue<ll, vll, greater<ll>> pq;
			for (ll l = 0; l < i; l++) {
				sum += v[l];
				if (v[l] < 0) pq.push(v[l]);
			}
			for (ll l = j; l < n; l++) {
				sum += v[l];
				if (v[l] < 0) pq.push(v[l]);
			}
			ll x = min(k - i - n + j, (ll)pq.size());
			while (x--) {
				sum -= pq.top();
				pq.pop();
			}
			ans = max(ans, sum);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,m,s,t;
#include<vector>
#include<queue>
#include<limits>
template<typename T>
vector<T>dijkstra(int s,const vector<vector<pair<int,T> > >&G,T INF=numeric_limits<T>::max())
{
	int n=G.size();
	vector<T>d(n,INF);
	vector<int>parent(n,-1);
	priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >P;
	d[s]=0;
	P.push(make_pair(d[s],s));
	while(!P.empty())
	{
		pair<T,int>p=P.top();P.pop();
		int v=p.second;
		if(d[v]<p.first)continue;
		for(const pair<int,T>&e:G[v])
		{
			int u=e.first;
			T cost=d[v]+e.second;
			if(d[u]>cost)
			{
				d[u]=cost;
				parent[u]=v;
				P.push(make_pair(d[u],u));
			}
		}
	}
	return d;
}
main()
{
	cin>>n>>m>>s>>t;
	s--,t--;
	vector<vector<pair<int,long> > >G(n),H(n);
	for(int i=0;i<m;i++)
	{
		int u,v,a,b;cin>>u>>v>>a>>b;u--,v--;
		G[u].push_back(make_pair(v,a));
		G[v].push_back(make_pair(u,a));
		H[u].push_back(make_pair(v,b));
		H[v].push_back(make_pair(u,b));
	}
	vector<long>ds=dijkstra(s,G);
	vector<long>dt=dijkstra(t,H);
	long ans=1e18;
	vector<long>s;
	for(int i=n;i--;)
	{
		ans=min(ans,ds[i]+dt[i]);
		s.push_back(1e15-ans);
	}
	for(int i=n;i--;)cout<<s[i]<<endl;
}


Measured memory_bytes: 19964
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ALL(v) (v).begin(), (v).end()
#define ios() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
constexpr ll MOD = 1e9+7;
constexpr ll INF = 1LL << 60;
constexpr int Inf = 1e9;
inline int in() {int x; cin >> x; return x;}
template <typename T> inline void out(const T& x) {cout << x << endl;}
template <class T> inline bool chmin(T &a, T b){if (a > b){a = b;return 1;}return 0;}
template <class T> inline bool chmax(T &a, T b){if (a < b){a = b;return 1;}return 0;}
//UP = 0;RIGHT = 1; DOWN = 2; LEFT =3;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b)
{
  if (a < b)
    gcd(b, a);
  int r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}

void eratos(bool * isPrime,int max){
  fill(isPrime,isPrime + max,true);
  isPrime[0] = false; 
  isPrime[1] = false; 
  for(int i=2; i<=max/i; ++i) 
      if(isPrime[i]) 
          for(int j=2; j<=max/i; ++j) 
              isPrime[i*j] = false;    
}
//

signed main()
{
  ios();
  int N;
  cin >> N;
  int max = 0;
  int cnt = 0;
  rep(i,N)
  {
    int H;
    cin >>H;
    if(H >= max)
    {
      cnt ++ ;
      max = H;
    }
  }
  cout <<cnt << endl;

  
}


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

int gcd(int a, int b) {
  int tmp;
  while ( a%b != 0 ) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}

int main() {
  int n, s;
  cin >> n >> s;
  int x[n+1];
  for ( int i = 0; i < n; i++ ) { cin >> x[i]; }
  x[n] = s;
  sort(x, x+n+1);
  int dif[n];
  for ( int i = 0; i < n; i++ ) {
    dif[i] = x[i+1] - x[i];
  }
  int ans = dif[0];
  for ( int i = 1; i < n; i++ ) {
    ans = gcd(ans, dif[i]);
  }

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


Measured memory_bytes: 1024
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
using namespace std;

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

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int count;
    count = 0;
    for(int i = 0; i < s.size() - 2; i++){
        if(s.at(i) == 'A'){
            if(s.at(i + 1) == 'B'){
                if(s.at(i + 2) == 'C'){
                    count++;
                }
            }
        }
    }
    cout << count << endl;
    
}

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



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

long long ans, a[100];

int main() {
//#ifndef ONLINE_JUDGE
//	freopen("a.in", "r", stdin);
//	freopen("a.out", "w", stdout);
//#endif
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i)
		for (int j = i + 1; j <= n; ++j)
			ans += a[i] * a[j];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,a[100005]; ll ans;
vector<int>val[2];
vector<int>all;
int main(){
	cin>>n;
	rep(i,n){
		cin>>a[i];
		val[i%2].pb(a[i]);
		all.pb(a[i]);
	}
	rep(i,2)sort(val[i].begin(),val[i].end());
	sort(all.begin(),all.end());
	set<int>S;
	for(int i=0;i<all.size();i+=2){
		S.insert(all[i]);
	}
	for(int i=0;i<val[0].size();i++){
		ans+=(S.find(val[0][i])==S.end());
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3828
#include <cstring>
#include <iostream>
#include <math.h>
#include <stdio.h>

#define arrayLength(array) (size_t)((sizeof array) / (sizeof array[0]))

int main() {
  int n = 0, m = 0, x = 0, y = 0, z = 0, a = 0, b = 0;

  char s[255];
  char t;

  //   scanf(" %d %d %d %d", &n, &m, &x, &y);
  scanf("%d %d", &a, &b);

  // 1.
  // x = (b / (a - 1));
  // printf("%d", b % (a - 1) > 1 ? x + 1 : x);

  // 2.
  // x = ((b-a) / (a - 1)) +;
  //

  if (b == 1) {
    printf("%d", 0);
    return 0;
  }

  // 3.
  x = 1;
  y = a;
  while (y < b) {
    y += (a - 1);
    x += 1;
  }

  printf("%d", x);

  return 0;
}


Measured memory_bytes: 256
N, L = [int(x) for x in input().split()]                                   
S = [input() for _ in range(N)]

def f(s, p=0):
    for i, c in enumerate("abcdefghijklmnopqrstuvwxyz"):
        if s[p] == c:
            if p == L - 1:
                return (i, )
            else:
                return (i, ) + f(s, p + 1)

print("".join([x[1] for x in sorted([(f(s), s) for s in S])]))

Measured memory_bytes: 9104
#include<iostream>
using namespace std;
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(i*m+j*n-i*j*2==k){
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;

ll n,m,a[N],b[N],lena,lenb,zero;

ll check(ll mid)
{
    ll ans = 0;
    if (mid < 0)
    {
        mid = abs(mid);
        for (int i = 1;i<=lena;i++)
        {
            ll num = a[i];
            if (mid % num == 0) num = mid / num;
            else num = mid / num + 1;
            ans += lenb - (lower_bound(b+1,b+lenb+1,num) - b - 1);
        }
    }
    else if (mid == 0) ans = zero * (lena + lenb) + lena * lenb + zero * (zero - 1) / 2;
    else
    {
        ans = zero * (lena + lenb) + lena * lenb + zero * (zero - 1) / 2;
        ll tmp1 = 0,tmp2 = 0;
        for (int i = 1;i<=lena;i++)
            tmp1 += upper_bound(a+i+1,a+lena+1,mid / a[i]) - a - i -1;
        for (int i = 1;i<=lenb;i++)
            tmp2 += upper_bound(b+i+1,b+lenb+1,mid / b[i]) - b - i -1;
        ans += tmp1 + tmp2;
    }
    return ans;
}

int main()
{
    scanf("%lld%lld",&n,&m);
    for (ll i = 1,u;i<=n;i++)
    {
        scanf("%lld",&u);
        if (u < 0) a[++lena] = -u;
        else if (u > 0) b[++lenb] = u;
        else zero++;
    }
    sort(a+1,a+lena+1);
    sort(b+1,b+lenb+1);
    ll r = max(a[lena] * a[lena-1],b[lenb] * b[lenb-1]),l = - a[lena] * b[lenb];
    while (l <= r)
    {
        ll mid = (l + r)>>1;
        ll num = check(mid);
        if (num >= m) r = mid - 1;
        else l = mid + 1;
    }
    cout<<l;
    return 0;
}

Measured memory_bytes: 1664
s = str(input())
t = str(input())
ans = []
for i in range(len(s)-len(t)+1):
    s_part = s[i:i+len(t)]
    check = True
    for j in range(len(t)):
        if (s_part[j] != "?"): 
            if (s_part[j] != t[j]):
                check = False
    if check:
        a = s[0:i]+t+s[i+len(t):len(s)]
        ans.append(a.replace("?","a"))
if ans == []:
    print("UNRESTORABLE")
else:
    print(sorted(ans)[0])

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

#define endl "\n"
#define int long long int
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define mod (int)(1e9+7)
#define T int
#define pi pair<int,int>
#define umap unordered_map<T,T>
#define uset unordered_set<T>
#define ff first
#define ss second
#define vi vector<int>
#define pb push_back
#define all(v) v.begin(),v.end()
#define setbit(n) __builtin_popcount(n)
#define toUpper(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define toLower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define flash ios_base::sync_with_stdio(false);cin.tie(NULL)


int lcm(int a, int b)
{
	return (a / __gcd(a, b) * b);
}


int32_t main() {

	flash;
	cout << fixed;
	cout.precision(10);

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif


	int k; cin >> k;

	if (k & 1 ^ 1) {
		cout << "-1" << endl;
		return 0;
	}

	int ans = 1;
	int s = 7;

	while (true) {

		if (s % k == 0) {
			cout << ans << endl;
			break;
		}

		if (ans > k) {
			cout << "-1" << endl;
			break;
		}

		s = (s % k) * 10 + 7;
		ans++;

	}





	return 0;

}







Measured memory_bytes: 3632
sx, sy, tx, ty = map(int, input().split())
dx = tx - sx
dy = ty - sy
print('R' * dx + 'U' * dy + 'L' * dx + 'D' * dy + 'L' + 'U' * (dy + 1) + 'R' * (dx + 1) + 'D' + 'R' + 'D' * (
        dy + 1) + 'L' * (dx + 1) + 'U')

Measured memory_bytes: 3060
import math
def c(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,m=map(int,input().split())
if n>=2 and m>=2:

    ans=c(n,2)+c(m,2)
elif n<=1 and m>=2:
    ans=c(m,2)
elif m<=1 and n>=2:
    ans=c(n,2)
elif n<=1 and m<=1:
    ans=0
print(ans)


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

ll x, y, a, b, c;
vector<ll> p, q, r;

int main(){
    cin >> x >> y >> a >> b >> c;
    p.resize(a);
    REP(i, a){
        cin >> p.at(i);
    }
    q.resize(b);
    REP(i, b){
        cin >> q.at(i);
    }
    r.resize(c);
    REP(i, c){
        cin >> r.at(i);
    }

    sort(p.begin(), p.end(), greater<ll>());
    sort(q.begin(), q.end(), greater<ll>());
    sort(r.begin(), r.end(), greater<ll>());

    priority_queue<ll, vector<ll>, greater<ll>> rq, gq;
    REP(i, x){
        rq.push(p.at(i));
    }
    REP(i, y){
        gq.push(q.at(i));
    }
    for(ll x : r){
        if(rq.top() > gq.top()){
            if(gq.top() < x){
                gq.pop();
                gq.push(x);
            }
        }else{
            if(rq.top() < x){
                rq.pop();
                rq.push(x);
            }
        }
    }

    ll ans = 0;
    while(!rq.empty()){
        ans += rq.top(); rq.pop();
    }
    while(!gq.empty()){
        ans += gq.top(); gq.pop();
    }
    cout << ans << endl;
    return 0;
}


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

int main()
{
   static long i,j,k;
   long n;
   long cnt = 0;
   long left,right,mid;
   long ans = 0;
   int a,b;
   static long e[10000];
   char op;
   for(i = 0;;i++) {
      scanf("%d %c %d",&a,&op,&b);
      if(op == '+')
         e[i] = a + b;
      else if(op == '-')
         e[i] = a - b;
      else if(op == '*')
         e[i] = a * b;
      else if(op == '/')
         e[i] = a / b;
      else break;
   }
   for(j = 0; j < i; j++) {
      printf("%ld\n",e[j]);
   }
   return 0;
}

Measured memory_bytes: 1032
import java.util.*;import java.io.*;import java.math.*;
public class Main{
  //↓見なくていいよ！ここから------------------------------------------
  static class InputIterator{
    ArrayList<String> inputLine = new ArrayList<String>(1024);
    int index = 0; int max;
    InputIterator(){
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      while(true){
        String read;
        try{
          read = br.readLine();
        }catch(IOException e){
          read = null;
        }
        if(read != null){
          inputLine.add(read);
        }else{
          break;
        }
      }
      max = inputLine.size();
    }
    boolean hasNext(){return (index < max);}
    String next(){
      if(hasNext()){
        String returnStr = inputLine.get(index);
        index++;
        return returnStr;
      }else{
        throw new IndexOutOfBoundsException("これ以上入力はないよ");
      }
    }
  }
  
  static InputIterator ii = new InputIterator();//リアクティブでは使えないので諦めてScanner使うこと
  static PrintWriter out = new PrintWriter(System.out);
  static void flush(){out.flush();}
  static void myout(Object t){out.println(t);}
  static void myerr(Object t){System.err.println(t);}
  static String next(){return ii.next();}
  static int nextInt(){return Integer.parseInt(next());}
  static long nextLong(){return Long.parseLong(next());}
  static ArrayList<String> nextStrArray(){return myHanSpSplit(next());}
  static ArrayList<String> myHanSpSplit(String str){return new ArrayList<String>(Arrays.asList(str.split(" ")));}
  static ArrayList<String> nextCharArray(){return mySingleSplit(next());}
  static ArrayList<String> mySingleSplit(String str){return new ArrayList<String>(Arrays.asList(str.split("")));}
  static ArrayList<Integer> nextIntArray(){
    ArrayList<Integer> ret = new ArrayList<Integer>();
    ArrayList<String> input = nextStrArray();
    for(int i = 0; i < input.size(); i++){
      ret.add(Integer.parseInt(input.get(i)));
    }
    return ret;
  }
  static ArrayList<Long> nextLongArray(){
    ArrayList<Long> ret = new ArrayList<Long>();
    ArrayList<String> input = nextStrArray();
    for(int i = 0; i < input.size(); i++){
      ret.add(Long.parseLong(input.get(i)));
    }
    return ret;
  }
  static String kaigyoToStr(String[] list){return String.join("\n",list);}
  static String kaigyoToStr(ArrayList<String> list){return String.join("\n",list);}
  static String hanSpToStr(String[] list){return String.join(" ",list);}
  static String hanSpToStr(ArrayList<String> list){return String.join(" ",list);}
  public static void main(String[] args){
    solve();
    flush();
  }
  //↑見なくていいよ！ここまで------------------------------------------
  static void solve(){//ここがメイン関数代わり
    ArrayList<Integer> one = nextIntArray();
    int N = one.get(0);
    int K = one.get(1);
    final long mod = 1000000007;
    long output = 0;
    for(long i = K; i <= N + 1; i++){
      long min = (i - 1) * i / 2;
      long max = i * N - ((i - 1) * i / 2);
      output += max - min + 1;
      output %= mod;
    }
    myout(output);
  }
  //Method addition frame start

  //Method addition frame end
}


Measured memory_bytes: 33012
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



//最大公約数
ll gcd(ll x,ll y){

	x = abs(x);
	y = abs(y);

	if(x < y){
		swap(x,y);
	}
	if(y == 0){
		return x;
	}else{
		return gcd(y,x%y);
	}
}

//最小公倍数
ll lcm(ll x,ll y){

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


int main(){

	ll A,B,C,D;
	scanf("%lld %lld %lld %lld",&A,&B,&C,&D);

	ll all = B-A+1;
	ll num_C = B/C-(A-1)/C;
	ll num_D = B/D-(A-1)/D;

	ll LCM = lcm(C,D);
	ll num_CD = B/LCM-(A-1)/LCM;

	printf("%lld\n",all-(num_C+num_D-num_CD));

	return 0;
}


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

int main() {
	int n,m,i,j;
	cin >> n >> m;
	vector<int> a(n);
	for(i=0; i<m; i++){
		cin >> j;
		a[j-1]++;
		cin >> j;
		a[j-1]++;
	}
	for(i=0; i<n; i++){
		cout << a[i] << endl;
	}
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int64_t abs(int64_t n) {
  if (n < 0) {
    n = -n;
  }
  return n;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}

int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 1;
  rep(i, n-1) {
    if (s.at(i) != s.at(i+1)) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC(T, v) static_cast<T>(v)
#define SI(v) SC(int, v.size())
#define SL(v) SC( LL, v.size())
#define RF(e, v) for(auto & e: v)
#define ei else if
#define UR assert(false)

// ---- ----

int h, w, n, si, sj;
string s, t;

void clamp(int & a, int l, int h) {
	setmax(a, l);
	setmin(a, h);
}

int main() {
	cin >> h >> w >> n >> si >> sj >> s >> t;
	si--; sj--;
	
	int il = 0, ih = h, jl = 0, jh = w;
	dec(i, n) {
		if(il == ih || jl == jh) { break; }
		if(t[i] == 'U') { ih++; clamp(ih, 0, h); }
		if(t[i] == 'D') { il--; clamp(il, 0, h); }
		if(t[i] == 'L') { jh++; clamp(jh, 0, w); }
		if(t[i] == 'R') { jl--; clamp(jl, 0, w); }
		
		if(s[i] == 'U') { il++; clamp(il, 0, h); }
		if(s[i] == 'D') { ih--; clamp(ih, 0, h); }
		if(s[i] == 'L') { jl++; clamp(jl, 0, w); }
		if(s[i] == 'R') { jh--; clamp(jh, 0, w); }
	}
	
	cout << (inID(si, il, ih) && inID(sj, jl, jh) ? "YES" : "NO") << endl;
	
	return 0;
}


Measured memory_bytes: 776
k, n = map(int, input().split())
As = list(map(int, input().split()))

sum = 0
long_distance = 0
distance = 0
for i in range(n):
    if i == n-1:
        distance = k - As[i] + As[0]
    else:
        distance = As[i+1] - As[i]
    sum += distance
    if long_distance < distance:
        long_distance = distance

print(sum-long_distance)

Measured memory_bytes: 26420
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
  int kotae=0;
  int N;
  cin >> N;
  int W[100];
  int S1=0;
  int S2=0;
  int S[N];
  for(int i=0;i<N;i++){
    cin >> W[i];
  }

  for(int T=0;T<N;T++){
    S1=0;
    for(int i=0;i<N;i++){
      S1=S1+W[i];
    }
    S2=S2+W[T];
    if(S1>=S2){
      S[T]=S1-S2;
      S[T]=S[T]-S2;
    }
    else{
      S[T]=S2-S1;
      S[T]=S[T]-S2;
    }
    if(S[T]<0){
      S[T]=S[T]*(-1);
    }
  }
  sort(S,S+N);
  cout << S[0] << endl;


  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

ll n;
ll m;
ll a;
map<ll, ll> mp;
set<ll> st;

int main() {
    mp[0] = 1;
    cin >> n >> m;
    ll sum = 0;
    imfor(i, n) {
        cin >> a;
        sum += a;
        sum %= m;
        st.insert(sum);
        if (mp.find(sum) == mp.end()) {
            mp[sum] = 1;
        }
        else {
            mp[sum] += 1;
        }
    }
    ll ans = 0;
    for (auto i : st) {
        if (mp.find(i) != mp.end()) {
            if (mp[i] > 1) {
                ans += mp[i] * (mp[i] - 1) / 2;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 7168
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

d = defaultdict(int)
for i in range(n):
    if a[i] >= 3200:
        d["free"] += 1
    elif a[i] >= 2800:
        d["red"] += 1
    elif a[i] >= 2400:
        d["ora"] += 1
    elif a[i] >= 2000:
        d["yellow"] += 1
    elif a[i] >= 1600:
        d["blue"] += 1
    elif a[i] >= 1200:
        d["rblue"] += 1
    elif a[i] >= 800:
        d["green"] += 1
    elif a[i] >= 400:
        d["brown"] += 1
    else:
        d["gray"] += 1

ans = 0
fr = 0
for i in d:
    if i == "free":
        fr += d[i]
    else:
        ans += 1

print(max(ans,1),ans+fr)

Measured memory_bytes: 3316