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

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

  vector<ll> d(n);
  for (int i = 0; i < n; i++) cin >> d[i];

  cin >> m;
  vector<ll> t(m);
  for (int i = 0; i < m; i++) cin >> t[i];

  multiset<ll> p;
  for (int i = 0; i < n; i++) p.insert(d[i]);

  bool ans = true;
  for (int i = 0; i < m; i++) {
    auto f = p.find(t[i]);
    if (f == p.end()) {
      ans = false;
      break;
    }
    p.erase(f);
  }
  if (ans) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 15640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
int main()
{
  //FAST IO       
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll k,a,b;
cin>>k;
cin>>a>>b;
ll flag=0;
for(ll i=a;i<=b;i++)
{
  if(i%k==0)
  {
    flag=-1;
    break;
  }
}
if(flag==0)
cout<<"NG"<<"\n";
if(flag==-1)
cout<<"OK"<<"\n";
return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;

int main(){
    int n,d[100000],k;
    cin >> n;
    rep(i,n) cin >> d[i];
    sort(d,d+n);
    k = d[n/2]-d[n/2 - 1];
    cout << k << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        String str = sc.next();
        char before = '0';
        int sum = 0;
        for (int i = 0; i < size ; i++) {
            char c = str.charAt(i);
            if(before != c){
                sum++;
                before = c;
            }
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 24056
#include <bits/stdc++.h>
#include <iostream>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;

#define nl '\n'
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: ", cout << to_string(__VA_ARGS__) << endl
/*compact version*/
template <typename T, size_t N> int SIZE(const T (&t)[N]) { return N; } template<typename T> int SIZE(const T &t) { return t.size(); } string to_string(string &s, int x1 = 0, int x2 = 1e9) { return '"' + ((x1 < s.size()) ? s.substr(x1, x2 - x1 + 1) : "") + '"'; } string to_string(const char* s) { string tmp(s); return to_string(tmp); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(char c) { return string({c}); } template<size_t N> string to_string(bitset<N> &b, int x1 = 0, int x2 = 1e9) { string t = ((x1 < b.size()) ? (b.to_string()).substr(x1, x2 - x1 + 1) : ""); reverse(begin(t), end(t)); return '"' + t + '"'; } template <typename A, typename... C> string to_string(A (&v), int x1 = 0, int x2 = 1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if (l_v_l_v_l == 0) res += nl; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2 - x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if (e != l) { if (rnk > 1) { res += nl; t_a_b_s = l_v_l_v_l; }; } else { t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if (l_v_l_v_l == 0) res += nl; return res; }
/*end of compact version*/


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input1.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
#endif

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

    while (t--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        int i = 1;
        while (a > 0 && c > 0) {
            if (i & 1) c -= b;
            else a -= d;
            i++;
            // dbg(a);
            // dbg(c);
        }
        // dbg(i);
        if (i & 1) cout << "No" << endl;
        else cout << "Yes" << endl;
    }

    return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define STEP 0.0005
// sort(a.begin(), a.end(), std::greater<int>());

int main()
{
    int n;
    cin >> n;
    vector<long long int> a;
    vector<long long int> b;
    rep(i, n)
    {
        int temp;
        cin >> temp;
        a.push_back(temp);
        b.push_back(temp);
    }
    SORT(a);
    double mid = (a[n / 2] + a[n / 2 - 1]) / 2.0;
    if(DEBUG) cout<<mid<<endl;
    int small = a[n / 2 - 1];
    int big = a[n / 2];
    rep(i, n)
    {
        if((double)b[i]<mid){
            cout<<big<<endl;
        }else{
            cout<<small<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 5476
N = int(input())
H = input().split()
H = [int(x) for x in H]
L = []

c = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    c +=1
  else:
    L.append(c)
    c = 0
    
L.append(c)
print(max(L))

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

using namespace std;

int main()
{
    int h , w , n , a;
    scanf("%d %d" , &h , &w);
    int res[h][w];
    int row = 0 , col = 0;
    bool inc = true;
    scanf("%d" , &n);
    for(int i = 1; i <= n; i ++){
        scanf("%d" , &a);
        for(int i1 = 0; i1 < a; i1 ++){
            res[row][col] = i;
            if(inc){
                if(col == w - 1){
                    row ++;
                    inc = false;
                }
                else{
                    col ++;
                }
            }else{
                if(col == 0){
                    row ++;
                    inc = true;
                }
                else{
                    col --;
                }
            }
        }
    }
    for(int i = 0; i < h; i ++){
        for(int i1 = 0; i1 < w; i1 ++){
            printf("%d " , res[i][i1]);
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int n, s[100009], q, t[50009], c = 0;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	cin >> q;
	for (int i = 0; i<q; i++) {
		cin >> t[i];
	}

	for (int i = 0; i < q; i++) {
		int left = 0;
		int right = n;
		int key = t[i];

		while (left < right) {
			int mid = (left + right) / 2;
			if (s[mid] == key) {
				c++;
				break;
			}
			else if (key < s[mid]) right = mid;
			else left = mid + 1;
		}
	}


	cout << c << endl;
}

Measured memory_bytes: 1744
#include "bits/stdc++.h"
 
using namespace std;

#define VI vector<int>
#define REP(i,n) for(int i=0; i<int(n); i++)
#define REREP(i,n) for(int i=int(n-1); i>=0; i--)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define Cout(str) cout << str << endl

int main(){
	int N;

	cin >> N;

	if(N%111 == 0) cout << N << endl;
	else cout << (N/111+1)*111 << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using vll = vector<ll> ;
#define all(v) v.begin(),v.end()
 
int main(){
  ll K;cin>>K;
  ll now=0;
  for(ll i=1;i<=1e6+5;++i){
    now = (now*10+7)%K;
    if(now==0){cout<<i<<endl;return 0;}
  }
  cout<<-1<<endl;
  }

Measured memory_bytes: 3592
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;
using static System.Console;

class Solver {
    Scanner sc = new Scanner();
    int ans = 0;
    int[,] g;
    int N;

    public void Solve() {
        N = sc.nextInt();
        var M = sc.nextInt();
        g = new int[N, N];
        for (int i = 0; i < M; i++) {
            var a = sc.nextInt();
            var b = sc.nextInt();
            g[a - 1, b - 1] = 1;
            g[b - 1, a - 1] = 1;
        }

        var lst = new List<int>();
        Dfs(lst, 1);

        WriteLine(ans);
    }

    void Dfs(List<int> lst, int n) {
        if (lst.Contains(n)) {
            return;
        }

        lst.Add(n);

        if (lst.Count == N) {
            ans++;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (g[n - 1, i] == 1) {
                Dfs(new List<int>(lst), i + 1);
            }
        }
    }
}



class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {

        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}

Measured memory_bytes: 15312
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;


typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string>vst;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef map<int,int> dct;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define all(ct) ct.begin() , ct.end()
#define endl "\n"
#define fr(i,a) for(auto i:a)
#define f(i,a,b) for(int i=a;i<b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define in(d,v) d.find(v)!=d.end()
#define mp make_pair
#define Pi 3.14159265
#define double
#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>

bool compare(pii a, pii b){
    if(a.first==b.first)return a.second<b.second;
    return a.first>b.first;
}

const int mod = 1e9 + 7;
const ll inf = ll(1e18);

ll modexp(ll x,ll n,ll k){
    if(n==0)return k;
    if(n%2==0)return modexp((x*x)%mod,n/2,k);
    return (x*modexp((x*x)%mod,n/2,k))%mod;
}

int main(){
    fastio;
    //clock_t tm = clock();
    int t,r,c,k,n,l,x,y,q;string s;
    cin>>n;
    cin>>s;
    f(i,0,s.length()){
        x = (s[i]-'A'+n)%26;
        cout<<(char('A'+x));
    }
    cout<<endl;
    //cout<<((clock()-tm)*1.0)/CLOCKS_PER_SEC<<endl;
}

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

//ライブラリ始まり

//定数

//円周率
const double PI = 3.1415926535897932384;

//天井
const int INF = 1000000000; // = 10^9
const ll LINF = 1000000000000000; // = 10^15

//ABC文字列
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZABC";
const string abc = "abcdefghijklmnopqrstuvwxyzabc";

//よくあるmodくん
const ll MOD = 1000000007; // = 10^9 + 7

//関数

//ctoi
int ctoi(char c){
  if (c == '0') {
    return 0;
  }
  if (c == '1') {
    return 1;
  } 
  if (c == '2') {
    return 2;
  } 
  if (c == '3') {
    return 3;
  }
  if (c == '4') {
    return 4;
  } 
  if (c == '5') {
    return 5;
  } 
  if (c == '6') {
    return 6;
  }
  if (c == '7') {
    return 7;
  } 
  if (c == '8') {
    return 8;
  } 
  if (c == '9') {
    return 9;
  }
  return -1;  
}

//素数判定
bool PN(int x) {
  if (x <= 1) {
    return false;
  }
  if (x == 2) {
    return true;
  }
  for (int i = 2; i < sqrt(x) + 1; i++) {
    if (x % i == 0) {
      return false;
    }
  }
  return true;
}

//ライブラリ終わり

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if (abs(A - B) <= D && abs (B - C) <= D) {
    cout << "Yes" << endl;
  }
  else if (abs(A - C) <= D) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}
  

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

int main()
{
    int A, B, C, max=0;
    cin >> A >> B >> C;

    max = std::max({A, B, C});
    if ((A+B+C)/2== (A + B + C) - max){
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    
}

Measured memory_bytes: 256
n=int(input())
s=input()

#毎ステップ毎にカウントする処理→TLE
# ans=10**6
# for i in range(1,N):
#   ans=min(ans,s[:i-1].count("W")+s[i+1:].count("E"))
# print(ans)
ans=[]
ans.append(s[1:].count("E"))
tmp=ans[0]
for i in range(1,n):
  if s[i]=="E":
    tmp-=1
  if s[i-1]=="W":
    tmp+=1
  ans.append(tmp)
print(min(ans))

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

struct node
{
    int id = -1;
    int left = -1;
    int right = -1;
    int parent = -1;
};

void findParent(vector<node> &n)
{
    for (int i = 0; i < n.size(); i++)
    {
        int j = n[i].left;
        if (j != -1)
        {
            n[j].parent = n[i].id;
        }

        j = n[i].right;
        if (j != -1)
        {
            n[j].parent = n[i].id;
        }
    }

    return;
}

int findRoot(vector<node> &n)
{
    int root = 0;
    for (int i = 0; i < n.size(); i++)
    {
        if (n[i].parent == -1)
        {
            root = n[i].id;
            return root;
        }
    }

    return root;
}

void preOrder(vector<node> &n, int num)
{
    cout << " " << n[num].id;

    int l = n[num].left;
    if (l != -1)
    {
        preOrder(n, l);
    }

    int r = n[num].right;
    if (r != -1)
    {
        preOrder(n, r);
    }
}

void inOrder(vector<node> &n, int num)
{
    int l = n[num].left;
    if (l != -1)
    {
        inOrder(n, l);
    }

    cout << " " << n[num].id;

    int r = n[num].right;
    if (r != -1)
    {
        inOrder(n, r);
    }
}

void postOrder(vector<node> &n, int num)
{
    int l = n[num].left;
    if (l != -1)
    {
        postOrder(n, l);
    }

    int r = n[num].right;
    if (r != -1)
    {
        postOrder(n, r);
    }

    cout << " " << n[num].id;
}

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

    vector<node> n(x);
    for (int i = 0; i < x; i++)
    {
        cin >> n[i].id >> n[i].left >> n[i].right;
    }
    sort(n.begin(), n.end(), [](node &left, node &right) {
        return left.id < right.id;
    });

    findParent(n);
    int root = findRoot(n);

    cout << "Preorder" << endl;
    preOrder(n, root);
    cout << endl;

    cout << "Inorder" << endl;
    inOrder(n, root);
    cout << endl;

    cout << "Postorder" << endl;
    postOrder(n, root);
    cout << endl;

    return 0;
}


Measured memory_bytes: 3112
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[111111];
int n;
int main()
{
	scanf("%s",s);
	n=strlen(s);
	if (n<2)
	{
		printf("-1 -1\n");
		return 0;
	}
	if (s[0]==s[1])
	{
		printf("1 2\n");
		return 0;
	}
	for (int i=2;i<n;i++)
	{
		if (s[i]==s[i-2])
		{
			printf("%d %d\n",i-1,i+1);
			return 0;
		}
		if (s[i]==s[i-1])
		{
			printf("%d %d\n",i,i+1);
			return 0;
		}
	}
	printf("-1 -1\n");
	return 0;
}

Measured memory_bytes: 384
import Data.List
import Data.Bool

main = print . solve . map (\xs -> (head xs, length xs)) . group . sort . map read . drop 1 . words =<< getContents

solve :: [(Int,Int)] -> Int
solve xls = maximum $ zipWith3 (\(a,al) (b,bl) (c,cl) -> bl + (bool 0 al $ abs(a-b) == 1) + (bool 0 cl $ abs(c-b) == 1)) xls' (drop 1 xls') (drop 2 xls')
    where
        xls' = [(0,0)] ++ xls ++ [(0,0)]


Measured memory_bytes: 17660
#include<iostream>
#define MAX 2048
using namespace std;
int main()
{
  while(true){
    int ans = 0;
    int pos=0;
    int n,m;
    int sg[MAX];
    scanf("%d%d", &n, &m);
    if(n == 0&&m==0)break;
    for(int i = 0; i < n; ++i){
      scanf("%d", &sg[i]);
    }
    bool end=false;
    for(int i = 0; i < m; ++i){
      int t;
      scanf("%d", &t);
      pos += t;
      if( pos >= n-1 ){
	if( !end ){
	  ans = i+1;
	  end = true;
	}
	continue;
      }else{
	pos += sg[pos];
	if( !end && pos >= n-1 ){
	  ans = i+1;
	  end=true;
	}
      }
    }
    printf("%d\n", ans);
  }
  return 0;
  
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

long long combination(const map<char, int> &map)
{
    long long ans = 1;
    for (long long i = map.size(); i >= map.size()-3; --i)
        ans *= i;
    return ans / 6ll;
}

int main()
{
    int N; cin >> N;
    vector<long long> count(5, 0);
    rep (i, 0, N) {
        string s; cin >> s;
        if (s[0] == 'M') ++count[0];
        else if (s[0] == 'A') ++count[1];
        else if (s[0] == 'R') ++count[2];
        else if (s[0] == 'C') ++count[3];
        else if (s[0] == 'H') ++count[4];
    }

    long long ans = 0;
    rep (i, 0, 5) {
        rep (j, 0, i) {
            rep (k, 0, j) {
                ans += count[i] * count[j] * count[k];
            }
        }
    }
    cout << ans << endl;
}

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

int main(){
    string s;
    cin >> s;
    int q;
    cin >> q;

    vector <string> ans(400100);
    int r = 200050;
    ans[200049] = s;
    int l = 200048;

    int rev = 0;

    rep(i,q){
        int a;
        cin >> a;
        if(a == 1){
            rev ++;
        }
        if(a == 2){
            int f;
            string c;
            cin >> f >> c;
            if(f == 1){//front
                if(rev % 2 == 0){
                    ans[l] = c;
                    l--;
                }
                else{
                    ans[r] = c;
                    r++;
                }
            }
            else{//back
                if(rev % 2 == 0){
                    ans[r] = c;
                    r++;
                }
                else{
                    ans[l] = c;
                    l--;
                }
            }
        }
    }
    
    if(rev%2==1){
        reverse(all(ans[200049]));
        for(int i=ans.size()-1; i>=0; i--){
            cout << ans[i];
        }
    }
    else{
        for(int i=0; i<ans.size(); i++){
            cout << ans[i];
        }
    }
}

Measured memory_bytes: 13184
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define INF 3e17
#define mod 1000000007
#define abs(x) ((x)>=0?(x):-(x))
#define y1 solai
#define fi first
#define se second
typedef long long ll;
void read(ll &x)
{
	scanf("%lld",&x);
}
void read(ll &x, ll &y)
{
	scanf("%lld%lld",&x,&y);
}
void read(ll &x, ll &y, ll &z)
{
	scanf("%lld%lld%lld",&x,&y,&z);
}
void print(ll x)
{
	printf("%lld ",x);
}
void println(ll x)
{
	printf("%lld\n",x);
}
const ll N=200000;
ll n,m,s,t,x,y,z,w[N+10],d1[N+10],cnt1[N+10],d2[N+10],cnt2[N+10],ans,len;
vector<ll>v[N+10],c[N+10];
priority_queue<pair<ll,ll> >q;
int main()
{
	//freopen("c.cpp","r",stdin);
 
	cin>>n>>m>>s>>t;
	for(ll i=1;i<=m;i++)
		read(x,y,z),v[x].pb(y),v[y].pb(x),c[x].pb(z),c[y].pb(z);
	for(ll i=1;i<=n;i++)
		d1[i]=d2[i]=INF;
	d1[s]=d2[t]=0;
	cnt1[s]=cnt2[t]=1;
	q.push({0,s});
	for(;!q.empty();)
	{
		x=q.top().se;
		q.pop();
		if(w[x])
			continue;
		w[x]=1;
		for(ll i=0;i<v[x].size();i++)
		{
			ll to=v[x][i],dist=c[x][i];
			if(d1[to]>d1[x]+dist)
				d1[to]=d1[x]+dist,cnt1[to]=cnt1[x],q.push({-d1[to],to});
			else if(d1[to]==d1[x]+dist)
				cnt1[to]+=cnt1[x],cnt1[to]%=mod;
		}
	}
	for(ll i=1;i<=n;i++)
		w[i]=0;
	q.push({0,t});
	for(;!q.empty();)
	{
		x=q.top().se;
		q.pop();
		if(w[x])
			continue;
		w[x]=1;
		for(ll i=0;i<v[x].size();i++)
		{
			ll to=v[x][i],dist=c[x][i];
			if(d2[to]>d2[x]+dist)
				d2[to]=d2[x]+dist,cnt2[to]=cnt2[x],q.push({-d2[to],to});
			else if(d2[to]==d2[x]+dist)
				cnt2[to]+=cnt2[x],cnt2[to]%=mod;
		}
	}
	ans=cnt1[t]*cnt1[t]%mod;
	len=d1[t];
	if(len==INF)
	{
		cout<<0;
		return 0;
	}
	for(ll i=1;i<=n;i++)
		if(len==d1[i]*2)
		{
			ans-=cnt1[i]*cnt2[i]%mod*cnt1[i]%mod*cnt2[i]%mod;
			while(ans<0)
				ans+=mod;
			while(ans>=mod)
				ans-=mod;
		}
	for(ll i=1;i<=n;i++)
		for(ll j=0;j<v[i].size();j++)
		{
			ll to=v[i][j],dist=c[i][j];
			if(d1[i]+d2[to]+dist==len&&d1[i]<(len+1)/2&&d2[to]<(len+1)/2)
			{
				ans-=cnt1[i]*cnt2[to]%mod*cnt1[i]%mod*cnt2[to]%mod;
				while(ans<0)
					ans+=mod;
				while(ans>=mod)
					ans-=mod;
			}
		}
	cout<<ans;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    vector<ll> S(N + 1, 0);
    rep(i, N) {
        S[i + 1] += S[i] + A[i];
    }
    if (K == 1) {
        cout << 0 << '\n';
        return;
    }
    map<ll, ll> cnt;
    ll ans = 0;
    cnt[0] = 1;
    rep(i, N) {
        ll s = S[i + 1];
        ll now = (s - i - 1) % K;
        if (now < 0) now += K;
        ans += cnt[now];
        cnt[now]++;
        if ((i + 1) - (K - 1) >= 0) {
            ll j = (i + 1) - (K - 1);
            ll s2 = S[j];
            ll prev = (s2 - j) % K;
            if (prev < 0) prev += K;
            cnt[prev]--;
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


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

int main(){
string s,t,u,v;  
int64_t a,b,c,d;
b=0;
cin>>s>>a;
for(int64_t i=0;i<a;i++){
   cin>>c;
  if(c==1){b++;}
  if(c==2){
    cin>>d>>t;
    if((b+d)%2==1){u=t+u;}
    else{v=v+t;}
  }
}
if(b%2==0){cout<<u+s+v<<endl;}
else{
  for(int64_t i=0;i<v.size();i++){
    cout<<v.at(v.size()-1-i);
  }
  for(int64_t i=0;i<s.size();i++){
    cout<<s.at(s.size()-1-i);
  }
  for(int64_t i=0;i<u.size();i++){
    cout<<u.at(u.size()-1-i);
  }
  cout<<endl;
  }
}

Measured memory_bytes: 4396
/***  بسم الله الرحمن ا لرحيم   ***/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_map>
#define endl                         '\n'
#define Ceil(x,y)             ((x+y-1)/y)
#define sz(s)               (int)s.size()
#define RT(x)           return cout<<x,0;
#define mem(x,y)    memset(x,y,sizeof(x))
#define all(v) ((v).begin()), ((v).end())
#define watch(x) cout<<#x<<" = { "<<x<<" }\n"
#define test int t;cin>>t;while(t--)
const int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
const int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
const double PI = acos(-1), EPS = 1e-7;
const int OO = 0x3f3f3f3f, N = 2e5 + 5, mod = 1e9 + 7;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll x, ll y) { return (!y) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return ((x / gcd(x, y)) * y); }
void file() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif  !ONLINEJUDGE
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

int n,k;
int memo[N];
vector<int>v;

int dp(int i) {
	if (i >= n)return OO;
	if (i + k >= n)return abs(v[i] - v[n - 1]);
	int& ret = memo[i];
	if (ret != OO)return ret;
	for (int j = 1; j <= k; j++) {
		if(j+i<n)ret = min(ret, dp(j+i) + abs(v[i] - v[i + j]));
	}
	return ret;
}
void solve() {
	cin >> n>>k;
	v = vector<int>(n);
	for (auto& t : v)cin >> t;
	mem(memo, OO);
	cout << dp(0) << endl;

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


Measured memory_bytes: 10668
#include<stdio.h>

typedef struct
{
	int iti;
	int suuti;
} SAIKORO;


int main(void)
{
	int kaisuu1, kaisuu2, kaisuu3;
	char hougaku[128] = {0};
	char kari1;
	SAIKORO date[6];
	SAIKORO kari2;

	kaisuu2 = 0;

	for (kaisuu1 = 0; kaisuu1 < 6; kaisuu1++)
	{
		date[kaisuu1].iti = kaisuu1 + 1;
		//printf("%d ", date[kaisuu1].iti);
	}
	scanf("%d %d %d %d %d %d ", &date[0].suuti, &date[1].suuti, &date[2].suuti, &date[3].suuti, &date[4].suuti, &date[5].suuti);
	scanf("%s", hougaku);
	while (kaisuu1 != 0)
	{
		kari1 = hougaku[kaisuu2];
		kaisuu2++;
		if (kari1 == 0)
		{
			for (kaisuu3 = 0; kaisuu3 < 128; kaisuu3++)
			{
				hougaku[kaisuu3] = 0;
			}
			break;
		}
		else
		{
			if (kari1 == 'E')
			{
				kari2 = date[2];
				date[2] = date[0];
				date[0] = date[3];
				date[3] = date[5];
				date[5] = kari2;
			}
			if (kari1 == 'W')
			{
				kari2 = date[3];
				date[3] = date[0];
				date[0] = date[2];
				date[2] = date[5];
				date[5] = kari2;
			}
			if (kari1 == 'S')
			{
				kari2 = date[4];
				//printf(" %d ", kari2.suuti);
				date[4] = date[5];
				//printf(" %d ", date[4].suuti);
				date[5] = date[1];
				//printf(" %d ", date[5].suuti);
				date[1] = date[0];
				//printf(" %d ", date[1].suuti);
				date[0] = kari2;
				//printf(" %d ", date[0].suuti);
			}
			if (kari1 == 'N')
			{
				kari2 = date[1];
				date[1] = date[5];
				date[5] = date[4];
				date[4] = date[0];
				date[0] = kari2;
			}
			/*for (kaisuu3 = 0; kaisuu3 < 6; kaisuu3++)
			{
				printf(" %d ", date[kaisuu3].suuti);
			}
			printf("\n");*/
		}
	}
	printf("%d\n", date[0].suuti);


	return 0;
}


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

using namespace std;

int main() {
	int a, b, time, cost, querys;
	int i, j, k, p, q, r, n, m;
	int times[100][100], costs[100][100];

	while (true) {
		cin >> n >> m;
		if (!n && !m)
			break;

		for (i = 0; i < m; i++) {
			for (j = 0; j < m; j++) {
				times[i][j] = (i == j) ? 0 : 1e6;
				costs[j][i] = (i == j) ? 0 : 1e6;
			}
		}

		for (i = 0; i < n; i++) {
			cin >> a >> b >> cost >> time;
			times[a - 1][b - 1] = time;
			times[b - 1][a - 1] = time;
			costs[a - 1][b - 1] = cost;
			costs[b - 1][a - 1] = cost;
		}

		for (k = 0; k < m; k++) {
			for (i = 0; i < m; i++) {
				for (j = 0; j < m; j++) {
					times[i][j] = min(times[i][j], times[i][k] + times[k][j]);
					costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j]);
				}
			}
		}

		cin >> querys;
		for (i = 0; i < querys; i++) {
			cin >> p >> q >> r;
			cout << (r ? times[p - 1][q - 1] : costs[p - 1][q - 1]) << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1236
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

bool isOK(int64_t num, int64_t pos, int64_t thr) {
  /* This is too slow.
       for (int i = 1; i <= num; ++i) {
         int64_t score = i * (pos + num - i);
         if (thr <= score) return false;
       }
       return true;
  */
  int64_t left = 1;
  int64_t right = num;
  while (left < right) {
    int64_t mid0 = left + (right - left) / 2;
    int64_t mid1 = mid0 + 1;
    int64_t score0 = mid0 * (pos + num - mid0);
    int64_t score1 = mid1 * (pos + num - mid1);
    if (score0 < score1)
      left = mid1;
    else
      right = mid0;
  }
  int64_t score = left * (pos + num - left);
  return (score < thr);
}

int64_t getMaxOK(int64_t num, int64_t pos, int64_t thr) {
  int64_t left = 1;
  int64_t right = num;
  while (left <= right) {
    int64_t mid = left + (right - left) / 2;
    if (isOK(mid, pos, thr)) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left - 1;
}

int main(void) {
  ios::sync_with_stdio(false);
  int Q;
  cin >> Q;
  vector<int> answer(Q);
  rep(i, Q) {
    int64_t A, B;
    cin >> A >> B;
    answer[i] = getMaxOK(A - 1, B + 1, A * B);
    answer[i] += getMaxOK(B - 1, A + 1, A * B);
  }
  rep(i, Q) cout << answer[i] << endl;
  return 0;
}

Measured memory_bytes: 3644
#coding:utf-8

N = int(raw_input())

tmp = map(int, raw_input().split())
D = tmp[0]
X = tmp[1]

total = 0
for i in range(N):
    current = int(raw_input())
    each = (D - 1) / current
    each += 1
    total += each
    
print (total + X)


Measured memory_bytes: 2568
#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 k, s; cin >> k >> s;
    ll ans = 0;
    rep(x, k+1) {
        rep(y, k+1) {
            int z = s - x - y;
            if(0 <= z && z <= k) ans++;
        }
    }
    cout << ans;
}


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

int main() {
	int a, b, c, d=0;
	cin >> a >> b >> c;
	if (a==b) d++;
	if (a==c) d++;
	if (b==c) d++;
	if (d==1) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll dp[100007];
int main(){
  ll n;
  cin >> n;
  vi h(n+1);
  h[0] = 0;
  for(ll i=1;i<=n;i++){
    cin >> h[i];
  }
  dp[0] = 0;
  dp[1] = 0;
  dp[2] = abs(h[2] - h[1]);
  for (ll i = 3; i <= n; i++){
    ll a = dp[i - 2] + abs(h[i] - h[i - 2]);
    ll b = dp[i - 1] + abs(h[i] - h[i - 1]);
    dp[i] = min(a, b);
  }
  print(dp[n]);
}


Measured memory_bytes: 1792
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
 
using namespace std;
 
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;}
 
const ll INF=1e15;
 
int main(){
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i,n){
        cin >> a[i];
        a[i]--;
    }
    vector<ll> ans;
    ll pos=0;
    ll times=0;
    map<ll,bool> h;
    while(times==0 || h.count(pos)==false){
        ans.push_back(pos);
        h[pos]=true;
        pos=a[pos];
        times++;
        //cout << times << " " << pos << endl;
    }
    
    ll m=ans.size();
    ll pos1=-1;
    rep(i,m){
        if(ans[i]==pos){
            pos1=i;
            break;
        }
    }
    //cout << pos1 << endl;
    if(k<=m-1){
        cout << ans[k]+1 << endl;
        return 0;
    }
    k-=(m-1);
    k%=(m-pos1); //ループの大きさ
    k=(k+(m-pos1)-1)%(m-pos1);
    
    cout << ans[pos1+k]+1 << endl;
    return 0;
} 


Measured memory_bytes: 18564
h, w = map(int,input().split())
n = int(input())
A = list(map(int,input().split()))

ANS = [[0] * w for i in range(h)]

clr = 1
pl = [0, 0]
v = 1

for i in range(h*w):
    #print(pl)
    ANS[pl[0]][pl[1]] = clr
    A[clr-1] -= 1
    if A[clr-1] == 0:
        clr += 1
    pl[1] += v
    if pl[1] < 0:
        pl[0] += 1
        pl[1] = 0
        v = 1
    elif pl[1] >= w:
        pl[0] += 1
        pl[1] = w-1
        v = -1

for i in range(h):
    print(" ".join(map(str, ANS[i])))

Measured memory_bytes: 39792
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int L;
    cin >> L;

    int h = 0;
    while (1 << (h + 1) <= L) {
        ++h;
    } 

    int n = h + 1;
    assert(n <= 20);

    vector<vector<int>> res;
    for (int i = 0; i + 1 < n; ++i) {
        res.emplace_back(vector<int>{i, i + 1, 1 << i});
        res.emplace_back(vector<int>{i, i + 1, 0});
    }

    int w = L;
    for (int i = 0; i < n; ++i) {
        if (L & (1 << i)) {
            w ^= 1 << i;
            if (w != 0) {
                res.emplace_back(vector<int>{i, n - 1, w});
            }
        }
    }

    cout << n << " " << res.size() << '\n';

    for (auto& E : res) {
        cout << E[0] + 1 << " " << E[1] + 1 << " " << E[2] << '\n';
    }

    return 0;
}

Measured memory_bytes: 256
/*
ID: barish21
LANG: C++14
TASK: test
*/

/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define intt long long

#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define IO ios_base::sync_with_stdio(false);cin.tie();

const intt max4 = 10004;
const intt maxx = 100005;
const intt max6 = 1000006;
const intt max7 = 10000007;

const intt lg4 = 13;
const intt lg5 = 17;
const intt lg6 = 20;

const intt INF = 2LL * 1000000000;
/***************/

/***Additional Functions***/

intt powmod (intt a, intt b, intt mod) {
    intt res = 1;
    a %= mod;
    for (; b; b >>= 1) {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
    }
    return res;
}

intt gcd (intt a, intt b) {
    while (b > 0) {
        intt t = a % b;
        a = b, b = t;
    }
    return a;
}

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

intt is_prime (intt n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (intt i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}

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

const intt initt = 0;

intt n, q;
intt t[maxx << 2], lazy[maxx << 2];

void init () {
    memset (lazy, -1, sizeof (lazy));
}

void relax (intt v, intt l, intt r) {
    t[v] += (r - l + 1) * lazy[v];
    if (l != r)
        lazy[v << 1] += lazy[v] + (lazy[v << 1] == -1), lazy[v << 1 | 1] += lazy[v] + (lazy[v << 1 | 1] == -1);
    lazy[v] = -1;
}

/*
void build (intt v, intt l, intt r) {
    if (l == r) {
        t[v] += initt;
        return;
    }
    intt mid = (l + r) >> 1;
    build (v << 1, l, mid);
    build (v << 1 | 1, mid + 1, r);
    t[v] = t[v << 1] + t[v << 1 | 1];
}
*/

void update (intt v, intt l, intt r, intt i, intt j, intt val) {
    if (lazy[v] != -1)
        relax (v, l, r);
    if (j < l || i > r)
        return;
    if (i <= l && r <= j) {
        lazy[v] += val + (lazy[v] == -1);
        relax (v, l, r);
        return;
    }
    intt mid = (l + r) >> 1;
    update (v << 1, l, mid, i, j, val);
    update (v << 1 | 1, mid + 1, r, i, j, val);
    t[v] = t[v << 1] + t[v << 1 | 1];
}

intt query (intt v, intt l, intt r, intt i, intt j) {
    if (j < l || i > r)
        return 0;
    if (lazy[v] != -1)
        relax (v, l, r);
    if (i <= l && r <= j)
        return t[v];
    intt mid = (l + r) >> 1;
    return query (v << 1, l, mid, i, j) +
           query (v << 1 | 1, mid + 1, r, i, j);
}

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    IO;
    init();
    cin >> n >> q;
    //build (1, 1, n);
    while (q --) {
        intt type, i, j, val;
        cin >> type;
        if (type == 0)
            cin >> i >> j >> val, update (1, 1, n, i, j, val);
        else
            cin >> i, cout << query (1, 1, n, i, i) << endl;
    }
    return 0;
}

Measured memory_bytes: 8308
#include<bits/stdc++.h>
#define d first
#define t second
using namespace std;typedef long l;l N,K,i,n,p,s;vector<pair<l,l>>v;bool u[1<<17];priority_queue<l,vector<l>,greater<l>>q;
main(){cin>>N>>K;v.resize(N);for(i=0;i<N;i++)cin>>v[i].t>>v[i].d;sort(v.rbegin(),v.rend());for(i=0;i<K;i++){s+=v[i].d;if(u[v[i].t])q.push(v[i].d);else u[v[i].t]=true,n++;}p=s+n*n;for(i=K;i<N;i++){if(!u[v[i].t]){if(!q.size())break;u[v[i].t]=true;s+=v[i].d;s-=q.top();q.pop();p=max(p,s+(++n)*n);}}cout<<p<<endl;}


Measured memory_bytes: 2556
#include <bits/stdc++.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

ll mod(ll a, ll b){
  ll ret=a%b;
  if(ret<0) ret+=b;
  return ret;
}

ll modpow(ll a,ll b,ll c){
  ll res=1;
  while(b>0){
    if(b&1) res=mod(res*a,c);
    a=mod(a*a,c);
    b>>=1;
  }
  return res;
}

int par[200001];
int r[200001];

void init(int n){
  for(int i=0;i<n;i++){
    par[i]=i;
    r[i]=0;
  }
}

int find(int x){
  if(par[x]==x){
    return x;
  }
  else{
    return par[x]=find(par[x]);
  }
}

void unite(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y) return;
  if(r[x]<r[y]){
    par[x]=y;
  }
  else{
    par[y]=x;
    if(r[x]==r[y]) r[x]++;
  }
}

bool same(int x,int y){
  return find(x)==find(y);
}

int main() {
  int n,m;
  cin>>n>>m;
  init(n);
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    unite(a,b);
  }
  map<int,int> memo;
  for(int i=0;i<n;i++){
    memo[find(i)]++;
  }
  int ans=0;
  for(auto itr=memo.begin();itr!=memo.end();itr++){
    ans=max(ans,itr->second);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 14484
import java.util.*;

public class Main {


    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        long h = sc.nextInt();
        long w = sc.nextInt();

        if (h==1 || w==1) {
            System.out.print(1);
            return;
        }

        if (h*w%2==0) {
            System.out.print(h*w/2);
        } else {
            System.out.print(h*w/2+1);
        }

    }
}



Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string s;
    cin >> n >> s;

    int ans = 1;
    for(int i = 0; i < n-1; i++){
        if(s.at(i) != s.at(i+1)){
            ans++;
        }
    }

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

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> L(N);
  for (int i = 0; i < N; i++) {
    cin >> L[i];
  }
  sort(L.begin(), L.end());
  int res = 0;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      int k = lower_bound(L.begin(), L.end(), L[i] + L[j]) - L.begin();
      res += max(0, k - j - 1);
    }
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  if (n == 1) dump(max(0, a[0]-x));
  else {
    ll res = 0;
    for (int i = 0; i < n-1; i++) {
      int dif = (a[i]+a[i+1])-x;
      if (dif > 0) {
	res += dif;
	ll t = min(a[i+1], dif);
	dif -= t; a[i+1] -= t;
	if (dif > 0) a[i] -= dif;
      }
    }
    dump(res);
  }
  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>

static const int N = 1000;

void trace(int A[], int n){
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

int main(){
  int n, i, j,k,v;
  int A[N+1];

  scanf("%d", &n);
 
  for ( i = 1; i <= n; i++ ) scanf("%d ", &A[i]);
  trace(A, n);
  for(i = 2 ;i <= n; i++){
    v = A[i];
    j = i-1;
    while( j >=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
      A[j+1]=v;
     }
    for ( k = 1; k <= n; k++ ){ 
       if(k<n)printf("%d ",A[k]);
       else printf("%d",A[k]);
    } 
    printf("\n");
   }   
  return 0;
}

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

using namespace std;
using ll = long long;
const ll mod = 1000000007;


int main()
{
    int n;
    cin >> n;
    vector<int> a(n + n);
    for(int i = 0; i < n + n; i++)cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans += a[i * 2];
    }
    cout << ans << endl;
}

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

using ll = long long;

//constant
const ll MOD = 1e+9 + 7;
const double EPS = 1e-10;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, s, e) for (ll i = s; i < e; i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// view vector
template<typename T> void view(T e) { std::cout << e << std::endl; }
template<typename T> void view(const std::vector<T>& v) { for (const auto& e : v) { std::cout << e << " "; } std::cout << std::endl; }
template<typename T> void view(const std::vector<std::vector<T> >& vv) { for (const auto& v : vv) { view(v); } }


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

int main(void) {

	ll N, K;
	cin >> N >> K;

	vector<ll> dp(N, 1e10);
	vector<ll> H(N);
	for (auto& h : H) {
		cin >> h;
	}

	dp[0] = 0;

	REP(i, N - 1) {
		FOR(j, 1, K+1) {
			if (i + j >= N) continue;
			dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]));
		}
	}

	cout << dp.back() << endl;

	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    string s;cin>>s;
    string key="keyence";
    int n=s.size();
    rep(i,n){
        for(int j=i;j<n;j++){
            string tmp=s.substr(0,i)+s.substr(j,n-j);
            if(tmp==key){
                cout<<"YES"<<endl;
                return 0;
            }
        }
    }
    cout<<"NO"<<endl;
    return 0;
    
}


Measured memory_bytes: 256
S = input()
cnt = 0
for s in S:
  if cnt % 2 == 0:
    if s not in ['R', 'U', 'D']:
      print('No')
      exit()
  else:
    if s not in ['L', 'U', 'D']:
      print('No')
      exit()
  cnt += 1
print('Yes')

Measured memory_bytes: 38484
#include <map>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <tr1/unordered_map>
#define mo 1000000007
#define num(x) (x>='0' && x<='9')
typedef unsigned long long ull;
typedef long long ll;
using namespace std::tr1;
using namespace std;
int read(){
    int p=0, q=1;
    char ch=getchar();
    while (!num(ch))
        (ch=='-'?q=-1:0),
        ch=getchar();
    while (num(ch)) p=p*10+ch-'0', ch=getchar();
    return p*q;
}
int power(ll a, int b){
	ll c=1;
	while (b){
		if (b&1) c=c*a%mo;
		a=a*a%mo;
		b>>=1;
	}
	return c;
}
#define N 1005
#define N2 N*N
#define M N*N*(25*2+1)
int n, m, sn, sm, en, em, cnt;
int f[N][N], dist[N2], l[N2];
int nex[M], nu[M];
char a[N][N];
inline bool check(int x, int y){
	return !(!x || x>n || !y || y>m || a[x][y]!='.');
}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void dfs(int x, int y, int d){
	f[x][y]=d;
	for (int j=0;j<4;j++)
		if (check(x+dx[j], y+dy[j]) && !f[x+dx[j]][y+dy[j]]) dfs(x+dx[j], y+dy[j], d);
}
void add(int u, int v){
	nex[++cnt]=nex[u];nex[u]=cnt;nu[cnt]=v;
	nex[++cnt]=nex[v];nex[v]=cnt;nu[cnt]=u;
}
int main(){
	n=read(), m=read();
	sn=read(), sm=read();
	en=read(), em=read();
	for (int i=1;i<=n;i++) scanf("%s", a[i]+1);
	cnt=0;
	for (int i=1;i<=n;i++)	
		for (int j=1;j<=m;j++)
			if (!f[i][j]&&a[i][j]=='.') dfs(i,j,++cnt);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (f[i][j])
			for (int x=-2;x<=2;x++)
				for (int y=-2;y<=2;y++)
					if (check(i+x,j+y) && f[i][j]!=f[x+i][y+j]) add(f[i][j], f[i+x][y+j]);
	dist[l[1]=f[sn][sm]]=1;
	for (int le=0, ri=1;le<ri && !dist[f[en][em]];){
		int u=l[++le];
		for (int j=nex[u];j;j=nex[j]){
			int v=nu[j];
			if (!dist[v]){
				dist[v]=dist[u]+1,
				l[++ri]=v;
				if (v==f[en][em]) break;
			}
		}
	}
	cout<<(dist[f[en][em]]?dist[f[en][em]]-1:-1)<<endl;
    return 0;
}

Measured memory_bytes: 38632
import sys
input = sys.stdin.readline

from collections import deque

N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
q = []
def check(x):
    if len(A[x]) == 0: return
    tmp = A[x][0]-1
    if A[tmp][0]-1 == x:
        if tmp < x: x,tmp=tmp,x
        q.append((x,tmp))
        return

for i in range(N):
    check(i)
day = 0
while len(q) > 0:
    day+=1
    q = list(set(q))
    prevQ=[]
    prevQ,q=q,prevQ
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        A[x].popleft()
        A[y].popleft()
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        check(x)
        check(y)
    
for i in range(N):
    if len(A[i]) != 0:
        print(-1)
        sys.exit()
print(day)


Measured memory_bytes: 76636
#include <stdio.h>
int Q(int a,int b){
	return (a>9)?
		0
	:
		(b<10)?
			printf("%dx%d=%d\n",a,b,a*b),
			Q(a,b+1)
			,0
		:
			Q(a+1,1);
	;
}
int main(){Q(1,1);}

Measured memory_bytes: 0
n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

x = min([a, b, c, d, e])
q = n//x
r = n%x

if r == 0:
    ans = 5 + q-1
else:
    ans = 5 + q
print(ans)

Measured memory_bytes: 38512
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <stdio.h>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);++i)
#define urep(i,a,n) for(ll i = (a);i>=(n);--i)
#define all(x) (x).begin(),(x).end()
#define INF 1e18
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N,M,X,Y,A,B,C,Q,K,R,W,H;
string S,T;
ll ans;
ll x[1000000];
ll y[1000000];
ll a[1000000];
ll b[1000000];
ll c[1000000];
ll t[1000000];
string s[10000];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
struct Edge{
	ll to,cost;
	 Edge(int to, int cost) : to(to), cost(cost) {}
};
typedef vector<vector<Edge> > AdjList;
AdjList graph;
vector<ll> dist;
ll in[1000000];
ll P[1000000];
int main() {
	cin>>N;
	rep(i,0,N){
		ll v;
		cin>>v;
		v=(i+v)%N;
		P[i]=v;
		in[v]++;
	}
	queue<ll> q;
	rep(i,0,N){
		if(in[i]==0)q.push(i);
	}
	ans =0;
	while(!q.empty()){
		ll num=q.front();
		q.pop();
		ans++;
		ll v = P[num];
		in[v]--;
		if(in[v]==0)q.push(v);
	}
	cout<<N-ans<<endl;
	return 0;
}


Measured memory_bytes: 4744