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

using ll = long long;
#define int long long
using P = pair<int, int>;

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
template<typename T = int>
T in() {T a; cin >> a; return a;}
/***** MAIN *****/
signed main() {
  int n, m, x;
  cin >> n >> m >> x;
  int prices[n];
  int books[n][m];
  REP(i,n) {
    cin >> prices[i];
    REP(j,m) {
      
      cin >> books[i][j];
    }
  }
  int ans = LLONG_MAX;
  for(int i = 1; i < (1<<n); ++i) {
    int price = 0;
    vector<int> exs(m,0);
    for(int j = 0; j < n; ++j) {
      if((i>>j)&1) {
        price += prices[j];
        REP(k,m) {
          exs[k] += books[j][k];
        }
      }
    }
    bool flag = true;
    for(int j = 0; j < m; ++j) {
      if(exs[j] < x) {
        flag = false;
        break;
      }
    }
    if(flag) {
      ans = min(ans, price);
    }
  }
  if(ans == LLONG_MAX) {
    cout << -1;
  } else {
    cout << ans;
  }
  cout << "\n";
  return 0;
}
/***** MAIN *****/


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

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for (int i=a; i<b; i++)
#define M00(i, a) for (int i=0; i<a; i++)
#define MOOd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define M00d(i,a) for (int i = (a)-1; i >= 0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _<< " _ " <<

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
typedef vector<int> vi;
typedef vector<ll> vll;

int main() { FAST
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ll n;
	cin >> n;
	ll handle = 26;
	int length = 1;
	while(handle < n) {
		n -= handle;
		handle *= 26;
		length++;
	}
	n--;
	vi dig;
	M00(i, length) {
		dig.pb(n % 26);
		n/=26;
	}
	M00(i, length) {
		char c = dig[length-1-i] + 'a';
		cout << c;
	}
	cout << endl;
}


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

int main()
{
        int n;
        cin>> n;
        map<string, int> arr;
        for(int i = 0; i< n; i++)
        {
                string s;
                cin >> s;
                arr[s]++;
        }
        cout << arr.size() << endl;

}


Measured memory_bytes: 19180
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>

using namespace std;

using VL = vector<long long>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;

using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;

int n;
VL a;
VVL memo;
VVB checked;

long long dfs(int a_idx, int head) {
// printf("%d %d\n", a_idx, head);
	if (a_idx == n) {
		return 0;
	} else if (checked[a_idx][head]) {
		return memo[a_idx][head];
	}

	int rest = n - 1 - a_idx;
	int tail = head + rest;

// printf("head %d, tail %d\n", head, tail);

	// 前をとる
	auto val1 = dfs(a_idx+1, head+1);
	// 後ろをとる
	auto val2 = dfs(a_idx+1, head);

	if (a_idx % 2 == 0) {
		// 先手 aを足して最大化
		memo[a_idx][head] = max(val1 + a[head], val2 + a[tail]);
	} else {
		// 後手 aを引いて最小化
		memo[a_idx][head] = min(val1 - a[head], val2 - a[tail]);
	}

	checked[a_idx][head] = true;
	return memo[a_idx][head];
}


int main() {
	cin >> n;

	a.assign(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	memo.assign(n + 1, VL(n + 1, 0));
	checked.assign(n + 1, VB(n + 1, false));

	auto ans = dfs(0, 0);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 72192
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int S, W; cin >> S >> W;
  if(S <= W){
    cout << "unsafe" << endl;
  }else{
    cout << "safe" << endl;
  }
}

Measured memory_bytes: 3648
using System;

class Program
{
    static void Main(string[] args)
    {
        var ks = Console.ReadLine().Split();
        var k = int.Parse(ks[0]);
        var s = int.Parse(ks[1]);

        var ans = 0;
        for (int x = 0; x <= k; x++)
        {
            for (int y = 0; y <= k; y++)
            {
                var z = s - x - y;
                if (0 <= z && z <= k)
                {
                    ans++;
                }
            }
        }

        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 11092
n = int(input())
a = [int(i) for i in input().split(" ")]

total = sum(a)//2

index = 1
while index <= n-1:
    total -= a[index]
    index += 2

answer = []
for i in range(n):
    answer.append(total*2)
    total = a[i] - total

print(" ".join(map(str,answer)))

Measured memory_bytes: 19140
#!/usr/bin/env python3
import math
a, b, n = map(int, input().split())
if n >= b:
    print(math.floor((a * (b - 1)) / b) - a * math.floor((b - 1) / b))
else:
    print(math.floor((a * n / b) - a * math.floor(n / b)))

Measured memory_bytes: 9052
#include <bits/stdc++.h>
#define INF LLONG_MAX
#define Int long long
#define rep(i,n) for(int i=0; i<n; ++i)
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;}

int main() {
  int N, M, X; cin >> N >> M >> X;
  vector<int> A(M); rep(i,M) cin >> A[i];
  int X2N=0, X20=0;
  // X to N
  for(int i=X; i<N; ++i) {
    if(count(A.begin(), A.end(), i)) ++X2N;
  }
  // X to 0
  for(int i=X; i>=0; --i) {
    if(count(A.begin(), A.end(), i)) ++X20;
  }
  cout << min(X2N, X20) << endl;
}

Measured memory_bytes: 764
#include <stdio.h>
int main(void)
{
	int H[1000],W[1000],i,j,k,l,H1=1,W1=1;
	for(i=0;(H1 != 0) || (W1 != 0);i++)
	{
		scanf("%d" "%d" ,&H1,&W1);
		H[i] = H1;
		W[i] = W1;
	}
	for(j=0;j<i-1;j++)
	{
		H1 = H[j];
		W1 = W[j];
		for(k=0;k < H1;k++)
		{
			if(k%2 == 0)
			{
				for(l=0;l < W1;l++)
				{
					if(l%2==0)
					{
						printf("#");
					}
					else
					{
						printf(".");
					}
				}
			}
			else
			{
				for(l=0;l < W1;l++)
				{
					if(l%2==0)
					{
						printf(".");
					}
					else
					{
						printf("#");
					}
				}
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 580
import copy

N = int(input())
S = list(input())

count = 0


#それぞれの文字数をカウントする
for i in range(len(S)):#どこで区切るか
    left = S[0:i]
    right = S[i:]
    left = set(left)
    right = set(right)
    sumsum = left & right
    sumsum = len(sumsum)
    if sumsum > count:
        count = copy.deepcopy(sumsum)

print(count)

Measured memory_bytes: 3700
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <sstream>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>

// namespace
using namespace std;
// namespace mp = boost::multiprecision;

// types
using pii = pair<int, int>;
using ll = long long int;
using ld = long double;
// using mpi = mp::cpp_int;
// using mpf = mp::number<mp::cpp_dec_float<1024>>;

int N, M;
int main() {
    cin >> N >> M;
    int ans = 0;
    ans += (M + N) * (M + N - 1) / 2;
    ans -= N * M;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;

int main() {
	int K;
	string S;
	cin >> S >> K;

	if (S.size() == 1) {
		cout << S << endl;
	}
	else {
		if (K == 1) cout << S.front() << endl;
		else {
			int n = -1;
			for (int i = 0; i < S.size(); i++) {
				if (S.at(i) != '1') {
					n = i + 1;
					break;
				}
			}
			//cout << "n:" << n << endl;

			if (n == -1) cout << 1 << endl;
			else {
				if (K < n) cout << S.at(K - 1) << endl;
				else cout << S.at(n - 1) << endl;
			}
		}
	}
}

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

int main()
{
    int N;

    cin >> N;
    vector<int> A(N);
    vector<int> B(N);

    for (int i = 0; i < N; i++)
    {
        cin >> A.at(i);
        B.at(A.at(i)-1) = i;
    }

    for (int i = 0; i < N;i++){
        cout << B.at(i)+1 << " ";
    }


}

Measured memory_bytes: 1536
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define bg begin()
#define en end()
#define vvl(n,m) vector<vector<ll> > a( n , vector<ll> (m))
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
ll gcd(ll a,ll b){
    if(a==0)
    return b;
    else
    return gcd(b%a,a);
}
ll maxSubArraySum(ll a[], ll size) 
{ 
    ll max_so_far = -1000000000000000, max_ending_here = 0; 
  
    for (ll i = 0; i < size; i++) 
    { 
        max_ending_here = max_ending_here + a[i]; 
        if (max_so_far < max_ending_here) 
            max_so_far = max_ending_here; 
  
        if (max_ending_here < 0) 
            max_ending_here = 0; 
    } 
    return max_so_far; 
} 
ll countPairs(ll arr[], ll n) 
{ 
    map<ll, ll> map; 
    for (ll i = 0; i < n; i++) {
        if (map.find(arr[i]-i) == map.end()) { 
            map[arr[i]-i] = 1; 
        } 
        else { 
            map[arr[i]-i]++; 
        } 
    }
    ll res = 0; 
    for (auto x : map) { 
        ll cnt = x.second; 

        res += ((cnt * (cnt - 1)) / 2); 
    } 
  
    return res; 
} 
ll findSubarraySum(ll arr[], ll n, ll sum) 
{ 
    unordered_map<ll, ll> prevSum; 
  
    int res = 0; 
  
    int currsum = 0; 
  
    for (int i = 0; i < n; i++) { 
        currsum += arr[i]; 
        if (currsum == sum)  
            res++;         
  
        if (prevSum.find(currsum - sum) !=  
                                  prevSum.end())  
            res += (prevSum[currsum - sum]);
        prevSum[currsum]++; 
    } 
  
    return res; 
} 
ll sod(ll x){
    ll r,sum=0;
    while(x>0){
        r=x%10;
        x/=10;
        sum+=r;
    }
    return sum;
}
long long modpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int main()
{
    fast
    ll n,i,j,k,mi,mid,ma,c=0;
    cin>>n;
    ll a[n];
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    for(i=0;i<n-2;i++){
        for(j=i+1;j<n-1;j++){
            for(k=j+1;k<n;k++){
                if(a[i]!=a[j] && a[j]!=a[k] && a[i]!=a[k]){
                    mi=min(a[i],a[j]);
                    mi=min(mi,a[k]);
                    ma=max(a[i],a[j]);
                    ma=max(ma,a[k]);
                    mid=a[i]+a[j]+a[k]-mi-ma;
                    if(mi+mid>ma){
                        c++;
                    }
                }
            }
        }
    }
    cout<<c;
}

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

using namespace std;
#define rep2(x,from,to) for(int x = (from); x < (to); ++(x))
#define rep(x,to) rep2(x,0,to)

int main() {
	char cup = 'A', x, y;
	while(scanf("%c,%c", &x, &y) != EOF) {
		if(x == cup) cup = y;
		else if(y == cup) cup = x;
	}
	cout << cup << endl;
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int main()
{
  do {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  } while (false);
  int k;
  cin >> k;
  if (k == 1) {
    cout << 1 << endl << 1 << endl;
  } else {
    int n = (k + 3) / 4 * 2;
    cout << n << endl;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        int r = (i + j) % n;
        if (i & 1) {
          r += n;
        }
        if (r >= k) {
          r -= n;
        }
        cout << r + 1 << " ";
      }
      cout << endl;
    }
  }
  return 0;
}


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


int color[100000];
bool finish[100000];
vector<int> tmp[100000];
vector<int> tmpweight[100000];

void coloring(int v){
  finish[v] = true;
  if(!tmp[v].empty()){
    for(int i = 0; i != tmp[v].size(); ++i) {
      int w = tmp[v][i];
      if(!finish[w]){
        if(tmpweight[v][i]%2 == 0){
          color[w] = color[v];
        }else{
          if(color[v]==0) color[w] = 1;
          else color[w] = 0;
        }
        coloring(w);
      }
    }
  }
}

int main() {

  int n;
  int u[100000];
  int v[100000];
  int w[100000];
  cin >> n;
  for(int i=0; i<n-1; i++){
    cin >> u[i] >> v[i] >> w[i];
    tmp[u[i]-1].push_back(v[i]-1);
    tmpweight[u[i]-1].push_back(w[i]);
    tmp[v[i]-1].push_back(u[i]-1);
    tmpweight[v[i]-1].push_back(w[i]);
  }

  for(int i=0;i<n; i++){
    color[i] = 0;
    finish[i] = false;
  }
  coloring(0);
  for(int i=0;i<n; i++){
    cout << color[i]<<"\n";
  }
  return 0;
}


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


int main(){
  int n,q;
  cin >> n >> q;
  string s;
  cin >> s;
  int count[n];
  count[0]=0;
  for(int i=1;i<n;i++){
    if(s[i-1]=='A' && s[i]=='C'){
      count[i] = count[i-1] + 1;
    }else count[i] = count[i-1];
  }
  int l,r;
  for(int i=0;i<q;i++){
    cin >> l >> r;
    cout << count[r-1]-count[l-1] << endl;
  }
  return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define inf 1000000000
using namespace std;
int read();
int n;
queue<int> q;
int fa[1003], deg[1003], x[1003], y[1003];
int f[1003][5003];
void insert(int u) { return --deg[u] ? void() : q.push(u); }

void update(int u, int a, int b) {
    for (int i = x[u]; i >= 0; --i) {
        if (i >= b)
            f[u][i] = min(f[u][i - a] + b, f[u][i - b] + a);
        else if (i < a)
            f[u][i] = inf;
        else
            f[u][i] = f[u][i - a] + b;
    }
}

int main() {
    n = read();
    for (int i = 2; i <= n; ++i) deg[fa[i] = read()]++;
    for (int i = 1; i <= n; ++i) x[i] = read();
    for (int i = 1; i <= n; ++i) deg[i] ? void() : q.push(i);
    while (!q.empty()) {
        int u = q.front(), v = fa[u];
        q.pop(), insert(v);
        if ((y[u] = f[u][x[u]]) >= inf) return puts("IMPOSSIBLE"), 0;
        if (!v) break;
        if (x[u] > y[u]) swap(x[u], y[u]);
        y[u] = min(y[u], inf);
        update(v, x[u], y[u]);
    }
    puts("POSSIBLE");
    return 0;
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}


Measured memory_bytes: 18048
a,b,c,x,y = map(int,input().split())

#1-AとBをそれぞれ買う場合
cost1 = a*x+b*y

#2-abを買えるだけ買う場合
cost2 = max(x,y)*2*c

#3-余りだけaまたはbで買う場合
cost_ab = min(x,y)*2*c    #abを買う
if  max(x,y) == x:
    tmp2 = (x-y)*a
else:
    tmp2 = (y-x)*b

cost3 = cost_ab + tmp2

print(min(cost1,cost2,cost3))

Measured memory_bytes: 3064
#![allow(non_snake_case)]
#![allow(unused_variables)]

fn main() {
    let (A, P): (i64, i64) = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap()
        )
    };

    let ans = (3 * A + P) / 2;

    println!("{}", ans);
}


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


#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, n) for (int i = 1; i <= (int)(n); i++)
using ll = long long;

/* vector<ll> v(N); 
    vector<pair<ll, ll> > p; ＃ソートした場合、１つ目でソート
　tie(b, a) = p.at(i); #pairを分割
    tasks.emplace_back(b, a)  ＃配列tasksの最後に(b,a)を追加
　xの二乗:  pow(x, 2.0) 
    小さい順: sort(v.begin(), v.end());
    逆順: reverse(v.begin(), v.end());
    int: -2,147,483,648 ～ 2,147,483,647
    ll: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
    // long long型の2次元配列(3×4要素の)の宣言
    vector<vector<ll>> data(3, vector<ll>(4));
*/
 
 //126~
 //

int main() {
  
  ll N,K, count=0, ans=0;
  string S;
  
  cin >> N >> K >> S;
  
  switch (S.at(K-1)){
    case 'A':
      S.at(K-1)='a';
      break;
    case 'B':
      S.at(K-1)='b';
      break;
    case 'C':
      S.at(K-1)='c';
      break;
    
    default:
      break;
  }

  cout << S << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N;
int A[100010];
int B[100010];

signed main(){
	cin>>N;
	REP(i,N){
		cin>>A[i];
	}
	int cnt=0;
	REP(i,N){
		if(A[i]<0){
			cnt++;
		}
	}
	int ans=0;
	if(cnt%2==0){
		REP(i,N){
			ans+=abs(A[i]);
		}
		cout<<ans<<endl;
	}
	else{
		int m=INF;
		int sum=0;
		REP(i,N){
			B[i]=abs(A[i]);
			m=min(m,B[i]);
			sum+=B[i];
		}
		cout<<sum-m*2<<endl;
	}
	return 0;
}


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

int constraints[3] = {-1, -1, -1};

int main()
{
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        if ((constraints[a] != -1 && constraints[a] != b) || (N > 1 && a == 0 && b == 0))
        {
            cout << -1;
            return 0;
        }
        constraints[a] = b;
    }
    
    if (N == 1)
        cout << (constraints[0] == -1 ? 0 : constraints[0]);
    else
        cout << (constraints[0] == -1 ? 1 : constraints[0]);
    for (int i = 1; i < N; i++)
    {
        cout << (constraints[i] == -1 ? 0 : constraints[i]);
    }
    // system("pause");
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int main() {
	int n;
	scanf("%d", &n);
	vector<int> X(n), Y(n), U(n);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d %c", &X[i], &Y[i], &U[i]);
	}
	int ans = INT_MAX;
	for (int tt = 0; tt < 4; ++tt) {
		map<int, set<int>> S, DR, UR;
		for (int i = 0; i < n; ++i) {
			if (U[i] == 'L') {
				S[Y[i]].insert(X[i]);
			} else if (U[i] == 'U') {
				DR[X[i] + Y[i]].insert(X[i]);
			} else if (U[i] == 'D') {
				UR[X[i] - Y[i]].insert(X[i]);
			}
		}
		for (int i = 0; i < n; ++i) {
			if (U[i] != 'R') continue;
			auto it = S[Y[i]].lower_bound(X[i]);
			if (it != S[Y[i]].end()) ans = min(ans, (*it - X[i]) * 5);
			it = DR[X[i] + Y[i]].lower_bound(X[i]);
			if (it != DR[X[i] + Y[i]].end()) ans = min(ans, (*it - X[i]) * 10);
			it = UR[X[i] - Y[i]].lower_bound(X[i]);
			if (it != UR[X[i] - Y[i]].end()) ans = min(ans, (*it - X[i]) * 10);
		}
		for (int i = 0; i < n; ++i) {
			if (U[i] == 'R') {
				U[i] = 'U';
			} else if (U[i] == 'U') {
				U[i] = 'L';
			} else if (U[i] == 'L') {
				U[i] = 'D';
			} else U[i] = 'R';
			swap(X[i], Y[i]);
			X[i] = -X[i];
		}
	}
	if (ans != INT_MAX) printf("%d\n", ans);
	else printf("SAFE\n");
}


Measured memory_bytes: 70420
import java.io.*;
 
class Main{
 public static void main(String[] arg) throws IOException{
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String str = br.readLine();
 
  int x = Integer.parseInt(str), h=x/3600, m, s;
  x %= 3600;
  m = x/60;
  x %= 60;
  s = x;
 
  System.out.println(h + ":" + m + ":" + s);
 }
}

Measured memory_bytes: 24172
import sys
h,w=[int(x) for x in input().rstrip().split()]
l=[]
al=[x for x in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"]
for i in range(h):
  s=[x for x in input().rstrip().split()]
  if "snuke" in s:
    ans=al[s.index("snuke")]+str(i+1)
print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

int main(){
  long a,b,c;
  cin>>a>>b>>c;

  cout << b + min(a+b+1, c) << endl;

  return 0;
}


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

int main() {
    string s, t;
    cin >> s;
    cin >> t;

    string ss = s+s;
    int ans = ss.find(t);
    if(ans == -1){
        cout << "No" << endl;

    }else{
        cout << "Yes" << endl;
    }    
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define Rep(n) for (ll _ = 0; _ < (ll)(n); _++)
#define fs first
#define sc second

template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min(a,(ll)b);}
template <class S> void print(vector<S> &v){for(ll i=0; i<(ll)v.size(); i++){cerr << v[i] << ' ';}cerr << endl;}
template <class S> void print(vector<vector<S>> &v) {for (ll i = 0; i < (ll)v.size(); i++) {for (ll j = 0; j < (ll)v[i].size(); j++) {cerr << v[i][j] << ' ';}cerr << endl;}}

int main(){
	int n; cin >> n;
	cout << ceil(n/1000.0)*1000 - n << endl;
}

Measured memory_bytes: 3796
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

int main() {
	int A; int B;
	while (~scanf("%d%d", &A, &B)) {
		int C; int D; int E; int F;
		scanf("%d%d%d%d", &C, &D, &E, &F);
		vector<bool> dp(F + max(C, D) + 1);
		dp[0] = true;
		rep(i, F) if (dp[i])
			dp[i + C] = dp[i + D] = true;
		vector<int> maxy(F + 1);
		rer(i, 1, F)
			maxy[i] = dp[i] ? i : maxy[i - 1];
		pair<double, pair<int, int>> ans{};
		rer(a, 0, F / (100 * A))rer(b, 0, F / (100 * B)) {
			int x = (a * A + b * B) * 100;
			int f = F - x;
			if (f < 0) continue;
			int y = maxy[min(f, x * E / 100)];
			amax(ans, make_pair(y * 1. / (x + y), make_pair(x + y, y)));
		}
		printf("%d %d\n", ans.second.first, ans.second.second);
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MAX = 1000001;
const lint MOD = 1000000007;
typedef pair<lint, lint> P;

vector<P> prime_factorize(lint N){
	vector<P> ans;
	for(lint a = 2; a*a <= N; a++){
		if(N%a == 0){
			lint ex = 0;
			while(N%a == 0){
				ex++;
				N /= a;
			}
			ans.push_back(P(a, ex));
		}
	}
	if(N != 1) ans.push_back(P(N, 1));
	return ans;
}

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

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint 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;
    }
}

lint COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

signed main(){
  lint N, M; cin >> N >> M;
  vector<P> vec = prime_factorize(M);
  lint ans = 1;
  COMinit();
  for(lint i = 0; i < vec.size(); i++){
    lint x = vec[i].second;
    ans *= COM(N + x - 1, N - 1);
    ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 23680
package main

import "fmt"

var mx, my, mz int

// 2018-07-29T20:57:30+0800
// 2018-07-29T21:18:07+0800
func main() {
	var N, Y int
	fmt.Scanf("%d%d", &N, &Y)
	//dp(N, Y/1000, 0, 0, 0)
	Y = Y / 1000
	for i := 0; i <= N; i++ {
		for ii := 0; ii <= N-i; ii++ {
			z := N - i - ii
			if 10*i+5*ii+z == Y {
				fmt.Println(i, ii, z)
				return
			}
		}
	}
	fmt.Println(-1, -1, -1)
}

func dp(N, Y, x, y, z int) bool {
	if N == 0 {
		if Y == 0 {
			mx = x
			my = y
			mz = z
			return true
		} else {
			mx = -1
			my = -1
			mz = -1
			return false
		}
	}
	if dp(N-1, Y-10, x+1, y, z) {
		return true
	}
	if dp(N-1, Y-5, x, y+1, z) {
		return true
	}
	if dp(N-1, Y-1, x, y, z+1) {
		return true
	}
	return false
}

Measured memory_bytes: 512
function main(input) {
  var temp = input.split(' ');
  var w = parseInt(temp[0]);
  var h = parseInt(temp[1]);
  var x = parseInt(temp[2]);
  var y = parseInt(temp[3]);
  var r = parseInt(temp[4]);

  var rangeMinX = 0 + r;
  var rangeMinY = 0 + r;
  var rangeMaxX = w - r;
  var rangeMaxY = h - r;
  if ( x <= rangeMaxX && x >= rangeMinX && y <= rangeMaxY && y >= rangeMinY) {
    console.log('Yes');
  } else {
    console.log('No');
  }
}

var x = require('fs').readFileSync('/dev/stdin', 'utf-8');
main(x);


Measured memory_bytes: 15340
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

b = input()
if b == 'A':
    print('T')
elif b == 'T':
    print('A')
elif b == 'G':
    print('C')
else:
    print('G')

Measured memory_bytes: 38256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int x = 1900 * m + 100 * (n - m);
		int p = (int)Math.pow(2, m);
		
		System.out.println(p * x);
	}

}


Measured memory_bytes: 22996
#include <stdio.h>

int main(void)
{
    int ans = 0;
    int a, b, c;

    scanf("%d%d%d", &a, &b, &c);

    if (a == b && b == c)
        ans = 0;
    else if (a == b || b == c || a == c)
        ans = 1;

    if (ans == 1)
        puts("Yes");
    else
        puts("No");

    return 0;
}

Measured memory_bytes: 128
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = [0]*M
y = [0]*M
c = [0]*M
for i in range(M):
    x[i], y[i], c[i] = map(int, input().split())
price = min(a) + min(b)
for j in range(M):
    cprice = a[x[j]-1] + b[y[j]-1] - c[j]
    if cprice < price:
        price = cprice
print(price)

Measured memory_bytes: 68844
import sys
from pprint import pprint

def solve(n, k, h):
    h.sort(reverse=True)
    target = h[k:] if k < n else [0]
    print(sum(target))

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().strip().split(" "))
    h = list(map(int,sys.stdin.readline().strip().split(" ")))
    
    solve(n, k, h)

Measured memory_bytes: 79192
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <functional>
#include <sstream>
#include <vector>
using namespace std;

int main(){
  string s, high, low;
  int L;
  vector<string> check;

  while(cin >> s >> L){
    if(s == "0" && L == 0) break;
    int cnt = 0;
    for(int i = s.size() ; i < L ; i++){
      s += '0';
    }
    
    check.clear();
    check.push_back(s);
    high = low = s;
    bool flag = false;
    while(1){
      cnt++;

      sort(high.begin(), high.end());
      sort(low.begin(), low.end());
      reverse(low.begin(), low.end());

      int l = atoi(high.substr(0, high.size()).c_str());
      int h = atoi(low.substr(0, low.size()).c_str());
    
      int res = h - l;
      ostringstream os;
      os << res;
 
      for(int i = 0 ; i < check.size() ; i++){
	if(os.str() == check[i]){
	  cout << i << ' ' << os.str() << ' ' << cnt-i << endl;
	  flag = true;
	  break;
	}
      }
      if(flag) break;
      
      check.push_back(os.str());
      high = low = os.str();
      
      for(int i = high.size() ; i < L ; i++){
	high += '0';
	low += '0';
      }
    }
  }
  return 0;
}

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

int main() {
    int N;
    ll K;
    cin >> N >> K;
    vector<int> A(N);
    rep(i,N) {
        int a;
        cin >> a;
        a--;
        A[i] = a;
    }

    int firstLoop = 0;
    int now = 0;
    int count = 0;
    vector<int> seen(N,0);
    while(1) {
        ++count;
        now = A[now];
        if(count >= K) {
            cout << now + 1 << endl;
            return 0;
        }

        if(seen[now] == 0) seen[now] = count;
        else break;
    }
    int LoopCount = count - seen[now];
    int rem = (K - seen[now]) % LoopCount;
    rep(i, rem) {
        ++count;
        now = A[now];
    }

    cout << now + 1 << endl;
    return 0;
}

Measured memory_bytes: 4764
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
#define x1 qeerdx
#define y1 qeerdy
 
#define lb lower_bound
#define ub upper_bound
 
#define endl '\n'
#define fast_in ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define mp  make_pair
#define pb  push_back
 
#define fi first
#define se second
 
#define   sz(x)  (int)x.size()
#define  all(x)  x.begin(), x.end()
#define  bit(x)  __builtin_popcountll(x)

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
               
typedef pair <int,int> pii;
 
const int inf = (int) 1e9+99999, mod = (int)1e9+7;
const ll linf = (ll) 2e18+99999;
 
int kob (int x, int y) { return ((ll)x * y) % mod; } 
int aza (int x, int y) { x -= y; if (x < 0) return x + mod; return x; } 
int kos (int x, int y) { x += y; if (x >= mod) return x - mod; return x; }
 
const int maxn = (int) 3e6, maxn2 = (int) 1e6+55;
 
static long holdrand = 1L;                         
void srand(unsigned int seed){holdrand = (long) seed;} 
int rand() {return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);}

void solve () {
	int a, b, c;
	cin >> a >> b >> c;
	bool bad = false;
	if (a == b && a != c) {
		bad = true;
	} else if (a == c && a != b) {
	    bad = true;
	} else if (c == b && a != c) {
		bad = true;
	}

	if (bad == true) {
		cout << "Yes";
	} else {
		cout << "No";
	}
}

main () { fast_in;
    int t = 1; //cin >> t;
    while (t --) {
    	solve ();    
    }
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define mp make_pair
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;

const int N = (int)(1e6 + 5);
const int LOG = (int)(20);

int n;
char s1[N], s2[N];

int main() {
	fast_io();
	// freopen("inp.in", "r", stdin);
	
	cin >> n;
	cin >> s1 + 1 >> s2 + 1;

	for(int i = 1; i <= n; i++) {
		bool fl = false;
		for(int j = i; j <= n; j++)
			if(s1[j] != s2[j - i + 1])
				fl = true;
		if(!fl) {
			cout << (n - i - 1) + 2 * i;
			return 0;
		}
	}
	cout << 2 * n;
}

Measured memory_bytes: 256
N = int(input())
S = input()
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

new_S = list()
for word in S:
    num = alpha.index(word)+N
    if num > 25:
        num -= 26
    new_S.append(alpha[num])
print(''.join(new_S))


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

using ll=long long;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m, x, y;
  cin >> n >> m >> x >> y;
  vector<int> X(n),Y(m);
  rep(i,n) cin >> X[i];
  rep(i,m) cin >> Y[i];
  int ans = 0;
  for(int z = x+1; z<=y ; z++) {
    bool J = 1;
    rep(j,n) if(!(z>X[j])) J = 0;
    rep(j,m) if(!(z<=Y[j])) J = 0;
    if(J) ans++;
  }
  if(ans) cout << "No War" << endl;
  else cout << "War" << endl;
  
}

Measured memory_bytes: 256
n, m = [int(x) for x in input().split()]

s = input()
c = n

h = []
while True:
	d = m
	while d > 0:
		if c - d >= 0:
			if s[c - d] == '0':
				break
		d -= 1

	if d == 0:
		print(-1)
		break
	
	c -= d
	h.append(str(d))
	if c == 0:
		h.reverse()
		print(' '.join(h))
		break

Measured memory_bytes: 46960
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;

struct xy{
  int x,y;
};

int main(){
  int m,n,ans=0;
  xy point[4];
  bool b;
  char clear[2];
  cin>>m>>n;
  char mp[501][501];
  mp[500][500]='.';
  rep(i,m){
    rep(j,n) cin>>mp[i][j];
  }
  
  while(1){
    b=true;
    rep(i,m){
      rep(j,n){

	if(mp[i][j]=='.'){
	  rep(k,4){
	    point[k].x=point[k].y=500;
	  }
	  
	  repi(k,i,m){
	    if(mp[k][j]!='.'){
	      point[0].x=k;
	      point[0].y=j;
	      break;
	    }
	  }
	  repi(k,j,n){
	    if(mp[i][k]!='.'){
	      point[1].x=i;
	      point[1].y=k;
	      break;
	    }
	  }
	  repn(k,i){
	    if(mp[k][j]!='.'){
	      point[2].x=k;
	      point[2].y=j;
	      break;
	    }
	  }
	  repn(k,j){
	    if(mp[i][k]!='.'){
	      point[3].x=i;
	      point[3].y=k;
	      break;
	    }
	  }

	  rep(k,4){
	    repi(l,k+1,4){
	    
	      if(mp[point[k].x][point[k].y]==mp[point[l].x][point[l].y]){
	
		if(point[k].x != 500 && point[l].x != 500){
		  
		  mp[point[k].x][point[k].y]=mp[point[l].x][point[l].y]='.';
	       
		  ans++;
		  
		  point[k].x=point[k].y=point[l].x=point[l].y=500;
		   
		  b=false;
		  //cout<<k<<" "<<l<<endl;
		}
	      }
	    }

	  }
	}
      }
    }
    if(b) break;
  }
  cout<<ans*2<<endl;	  

  return 0;
}












Measured memory_bytes: 3368
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int N, K;
  cin >> N >> K;
  vector<int> v;
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);
  }

  vector<ll> R(N+1,0);
  rep(i,N){
    R[i+1] = R[i] + v[i];
  }
  vector<ll> Q(N+1,0);
  Q[0] = 1;
  REP(i,1,N+1){
    Q[i] = (R[i] - ((i-1)%K) + K) % K;

  }

  ll ret = 0;
  map<int,int> m;
  rep(i,N+1){
    if(i>=K) m[Q[i-K]]--;
    ret += m[Q[i]];
    m[Q[i]]++;
  }


  cout << ret << endl;
  
  return 0;
}



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

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

//const int MOD = 1e9 + 7;
const int MOD = 998244353;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

template<class T> bool chmax(T &a, const T &b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if(a > b) { a = b; return true; } return false; }

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll N, K; cin >> N >> K;
    vl L(K), R(K); REP(i, K) cin >> L[i] >> R[i];
    vl dp(N+1, 0);

    REP(j, K)
    {
        if(1+L[j] <= N) dp[1+L[j]] += 1;
        if(1+R[j]+1 <= N) dp[1+R[j]+1]--;
    }

    for(int i = 2; i <= N; i++)
    {
        dp[i] += dp[i-1];
        dp[i] %= MOD;
        if(dp[i] != 0)
        {
            REP(j, K)
            {
                if(i+L[j] <= N) 
                {
                    dp[i+L[j]] += dp[i];
                    dp[i+L[j]] %= MOD;
                }
                if(i+R[j]+1 <= N) 
                {
                    dp[i+R[j]+1] -= dp[i];
                    dp[i+R[j]+1] = (dp[i+R[j]+1] + MOD) % MOD;
                }
            }
        }
    }
    cout << dp[N] % MOD << endl;
}

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

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


int main(void) {
  char in[1024], out[1024];
  cin >> in;

  int p = 0;
  REP(i, strlen(in)) {
    if(in[i] == '0') {
      out[p++] = '0';
    }
    if(in[i] == '1') {
      out[p++] = '1';
    }
    if(in[i] == 'B') {
      if(p > 0) p--;
    }
  }
  out[p] = '\0';

  cout << out << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

#define MOD 1000000007
#define INF 2000000000

int GLL(LL& x) {
    return scanf("%lld", &x);
}

int GI(int& x) {
    return scanf("%d", &x);
}

string s, t; int q;

const int MAXL = 100005;
int cnts[MAXL][2], cntt[MAXL][2];

void canon(PII& p) {
    int m = min(p.FF, p.SS);
    p.FF -= m;
    p.SS -= m;

    p.FF %= 3;
    p.SS %= 3;

    if (p.FF == 2) {
        p.SS = 1;
        p.FF = 0;
    }
    if (p.SS == 2) {
        p.FF = 1;
        p.SS = 0;
    }
}

int main() {
    cin >> s >> t >> q; s = '^' + s; t = '^' + t;

    memset(cnts, 0, sizeof cnts);
    memset(cntt, 0, sizeof cntt);

    FOR1(i, s.size() - 1) {
        FORN(j, 2) cnts[i][j] = cnts[i-1][j];

        if (s[i] == 'A') cnts[i][0]++;
        if (s[i] == 'B') cnts[i][1]++;
    }

    FOR1(i, t.size() - 1) {
        FORN(j, 2) cntt[i][j] = cntt[i-1][j];

        if (t[i] == 'A') cntt[i][0]++;
        if (t[i] == 'B') cntt[i][1]++;
    }

    int a, b, c, d;

    while (q--) {
        GI(a); GI(b); GI(c); GI(d);

        PII sab = MP(cnts[b][0] - cnts[a-1][0], cnts[b][1] - cnts[a-1][1]);
        PII tab = MP(cntt[d][0] - cntt[c-1][0], cntt[d][1] - cntt[c-1][1]);

//        cout << q << " " << sab.FF << " " << sab.SS << endl;
//        cout << q << " " << tab.FF << " " << tab.SS << endl;

        canon(sab);
        canon(tab);

//        cout << q << " " << sab.FF << " " << sab.SS << endl;
//        cout << q << " " << tab.FF << " " << tab.SS << endl;

        if (sab == tab) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
    
    return 0;
}

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

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FOR(i,a,b) for(int i=a; i<= b; ++i)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define Ld long double

using namespace std;
typedef long long ll;
const int mx = 1001;
int a[mx];
vector<int> v;

int main(){
    optimize();
    string s,t;
    cin>>s>>t;
    int n = s.length(),m = t.length();

    ll cnt = 0;
    for(int i=0; i<=(n-m); i++){
        for(int j=0; j<m; j++){
            if(s[i+j] != t[j]){
                cnt++;
            }
        }
        v.push_back(cnt);
        cnt = 0;
    }
    int mn = 1005;
    for(auto v1: v){
        if(mn > v1) mn = v1;
    }
    cout<<mn<<endl;
    return 0;
}


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

using namespace std;
#define INF  (2000000005)
#define BUF (1000)
#define ll long long 

int n,k;
vector<int> x,y;
vector<pair<int,int>> pv;

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

	for(int i=0;i<n;i++){
		int tx,ty;
		cin>>tx>>ty;
		x.push_back(tx);
		y.push_back(ty);
	}	

	ll ans=INF;
	ans*=INF;
	for(auto u1:x) for(auto u2:x){
		for(auto v1:y) for(auto v2:y){
			
			int cnt = 0;
			for(int i=0;i<n;i++){
				if(x[i]>u1&&x[i]>u2) continue;
				if(x[i]<u1&&x[i]<u2) continue;
				if(y[i]<v1&&y[i]<v2) continue;
				if(y[i]>v1&&y[i]>v2) continue;

				cnt++;
			}
			if(cnt>=k){
				ll tmp=(ll)abs(v1-v2)*(ll)abs(u1-u2);
				if(tmp<ans) ans = tmp;
			}				
		}
	}

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


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define fcout(d) cout << fixed << setprecision(d)
#define repU(i,s,t) for(int i = (int)(s); i <= (int)(t); ++i)
#define repD(i,t,s) for(int i = (int)(t); i >= (int)(s); --i)
#define rep(i,n) repU(i,0,n - 1)
#define rep1(i,n) repU(i,1,n)
#define all(v) begin(v),end(v)
#define vct vector
#define prique priority_queue
#define l_bnd lower_bound
#define u_bnd upper_bound
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define fir first
#define sec second
#define qceil(n,d) ((n) > 0 ? ((n) - 1) / (d) + 1 : (n) / (d))
#define parity(a,b) (a & 1 == b & 1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;

const pii dir[] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} };
const int inf32 = (1 << 30) - 1;
const ll inf64 = (1LL << 62) - 1;
const int mod = 1e9 + 7;

const void fail(){ cout << -1 << endl, quick_exit(0); }

int K,A[100100];
ll N[2][2];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> K;
	A[0] = 1;
	rep1(i,K) cin >> A[i];
	if(A[K] != 2) fail();
	N[0][0] = N[0][1] = 2;
	int t = 0;
	repD(g,K - 1,0){
		ll l = N[t][0],r = N[t][1] + A[g + 1] - 1;
		t = 1 - t;
		N[t][0] = qceil(l,A[g]) * A[g];
		N[t][1] = r / A[g] * A[g];
		if(N[t][0] > N[t][1]) fail();
	}
	cout << N[t][0] << ' ' << N[t][1] << endl;
}



Measured memory_bytes: 640