akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <limits>
#include <climits>
#include <utility>
#include <algorithm>
#include <numeric>

using namespace std;

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

int main()
{
    int N, K;
    cin >> N >> K;

    string S;
    cin >> S;

    --K;

    if (S[K] == 'A') {
        S[K] = 'a';
    } else if (S[K] == 'B') {
        S[K] = 'b';
    } else if (S[K] == 'C') {
        S[K] = 'c';
    } 

    cout << S << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

		int n = sc.nextInt();
		int a, b;
		int m = 0;

		for (int i = 1; i <= n / 2; i++) {
			a = i;
			b = n - a;
			if (a == b) continue;
			//System.out.println(a + " " + b);
			m++;
		}

		System.out.println(m);
	}
}


Measured memory_bytes: 23892
import numpy as np
N,M=list(map(int,input().split()))
X=np.sort(np.array(list(map(int,input().split()))))

if N>=M:
    print(0)
else:
    L=np.sort(np.diff(X))
    ans=X[-1]-X[0]
    for i in range(1,N):
        ans-=L[-i]
    print(ans)  

Measured memory_bytes: 23024
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace contest_Csharp
{
    class Program
    {
        public static (long m,long s)[,] dp;

        static void Main(string[] args)
        {
            checked
            {
                var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
                Console.SetOut(sw);

                var vals = Console.ReadLine().Split(' ').
                    Select(x => int.Parse(x)).ToList();

                var K = vals[0];
                int num = 7%K;

                var ans = 1;
                var checker = new int[K]; 
                while (true)
                {
                    if (num % K == 0)
                        break;
                    ans++;
                    checker[num] = 1;
                    num = (num * 10 + 7) % K;
                    if (checker[num] != 0)
                    {
                        ans = -1;
                        break;
                    }

                }
                
                
                Console.WriteLine(ans);

                Console.Out.Flush();
            }




        }
    }
}




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

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

  bool y = false;
  
  for(int i=0; i<N; i++){
    string A;
    cin >> A;
    if(A == "Y"){
      y = true;
    }
  }

  if(y){
    cout << "Four" << endl;
  }
  else
    cout << "Three" << endl;
}



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

int main()
{
    array<int, 3> a;
    for (int i = 0; i < 3; ++i)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    if (a[0] == 5 && a[1] == 5 && a[2] == 7)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    
}

Measured memory_bytes: 3636
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]

uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0]-1,AB[i][1]-1)
ufr = uf.roots()
ans = 0
for i in ufr:
    ans = max(ans,uf.size(i))
print(ans)

Measured memory_bytes: 110616
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 10**7+9
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

n,r = LI()
if n<10:
    print(r+(100*(10-n)))
else:
    print(r)

Measured memory_bytes: 5328
/*
 * 2600.cc: Koto Distance
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

typedef pair<int,int> pii;

/* global variables */

pii xrs[MAX_N], yrs[MAX_N];

/* subroutines */

void print_piis(int n, pii rs[]) {
  for (int i = 0; i < n; i++)
    printf("(%d,%d)", rs[i].first, rs[i].second);
  putchar('\n');
}

/* main */

int main() {
  int n, w, h;
  cin >> n >> w >> h;

  for (int i = 0; i < n; i++) {
    int xi, yi, wi;
    cin >> xi >> yi >> wi;
    xrs[i].first = xi - wi;
    xrs[i].second = xi + wi;
    yrs[i].first = yi - wi;
    yrs[i].second = yi + wi;
  }
  sort(xrs, xrs + n);
  sort(yrs, yrs + n);
  //print_piis(n, xrs); print_piis(n, yrs);

  bool ok = true;
  int mx = 0, my = 0;

  for (int i = 0; ok && i < n; i++) {
    int &x0 = xrs[i].first, &x1 = xrs[i].second;
    if (mx < x0) ok = false;
    else {
      if (mx < x1) mx = x1;
      if (mx >= w) break;
    }
  }
  if (mx < w) ok = false;

  if (! ok) {
    ok = true;
    for (int i = 0; ok && i < n; i++) {
      int &y0 = yrs[i].first, &y1 = yrs[i].second;
      if (my < y0) ok = false;
      else {
	if (my < y1) my = y1;
	if (my >= h) break;
      }
    }
    if (my < h) ok = false;
  }

  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 2724
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
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;}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    ll n, k;
    cin >> n >> k;
    ll ans = 0;
    FOR(i, k, n + 2) {
        ll mn = (ll)i * (i - 1) / 2;
        ll mx = n * (n + 1) / 2 - (n - i) * (n - i + 1) / 2;
        // cout << i << ": " << mn << "/" << mx << endl;
        ll x = (mx - mn + 1) % MOD;
        if (x < 0) x += MOD;
        ans += x;
        ans %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3652
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define PI 3.141592653589793238
#define INF 1050000000

using vi = vector<int>;


int main() {

	int N, A, B;

	cin >>N  >>A>>B;

	if (N * A <= B) {
		cout << N*A << endl;
	}
	else {
		cout << B << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define INF 2000000
int a[1000][1000],t[1000];

int MIN(int x,int y){
    if(x > y)return y;
    else return x;
}

void MatrixChain(int num){
    int i,j,l,k;
    for(i = 1; i <= num; i++)
        a[i][i] = 0;
    
    for(l = 2; l <= num; l++){
        for(i = 1; i <=num; i++){
            j = i + l - 1;
            a[i][j] = INF;
            for(k = i; k <= j; k++){
                a[i][j] = MIN(a[i][j], a[i][k] + a[k+1][j] + t[k]*t[i-1]*t[j]);
            }
        }
    }
}

int main(){
    int num,i;
    scanf("%d",&num);
    
    for(i = 1; i <= num; i++)
        scanf("%d %d",&t[i-1],&t[i]);

    MatrixChain(num);
    printf("%d\n",a[1][num]);
    
    return 0;
}




Measured memory_bytes: 2120
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def kaibun(s):
    return s == s[::-1]


def solve(S: str):
    N = len(S)

    if not kaibun(S):
        no()
        return

    s = S[:(N-1)//2]
    # print(s)
    if not kaibun(s):
        no()
        return

    s = S[(N+1)//2:]
    # print(s)
    if not kaibun(s):
        no()
        return

    yes()
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

int main(){
    Init();
    ll n; cin >> n;
    set<ll> st;
    rep(i, n){
        ll in; cin >> in;
        st.insert(in);
    }
    cout << st.size() << endl;
}

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

li = [0]*n
for i in range(n):
    s = input()
    li[i] = sorted(s)

li.sort()

cnt = 0
con = 0
pre = ""
for s in li:
    if pre == s:
        con += 1
        cnt += con
    else:
        con = 0
    pre = s

print(cnt)


Measured memory_bytes: 95948
<?php
$N = trim(fgets(STDIN));
$S = str_split(trim(fgets(STDIN)));
$ans =0;
for($i=0;$i<$N;$i++){
$num = 0;
$a = array_slice($S,0,$i+1);
$b = array_slice($S,$i+1);
$a = array_unique($a);
$b = array_unique($b);
$a = array_values($a);
$b = array_values($b);
  for($j=0;$j<count($a);$j++){
  if (in_array($a[$j],$b)==true){
    $num += 1;
  }
}
if($ans<$num){
  $ans = $num;
}
}
echo $ans;


Measured memory_bytes: 3700
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
    bool dp[2][100010]={};
    dp[0][0]=dp[1][0]=1;
    int n; cin>>n;
    int h[100010];
    for(int i=0; i<n; i++) cin>>h[i];
    for(int i=1; i<n; i++){
        if(dp[0][i-1]){
            if(h[i-1]<=h[i]) dp[0][i]=1;
            if(h[i-1]<=h[i]-1) dp[1][i]=1;
        }
        if(dp[1][i-1]){
            if(h[i-1]-1<=h[i]) dp[0][i]=1;
            if(h[i-1]-1<=h[i]-1) dp[1][i]=1;
        }
    }
    if(dp[0][n-1] || dp[1][n-1]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 768
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

struct node {
  int key;
  node *parent, *right, *left;
};

node *NIL, *root;

void insert(int k) {
  node *y = NIL;
  node *x = root;
  node *z = (node *)malloc(sizeof(node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while (x != NIL) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  z->parent = y;
  if (y == NIL) {
    root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
}

void find(int k) {
  node *x = root;
  while (x != NIL) {
    if (x->key == k) {
      cout << "yes" << endl;
      return;
    } else if (k < x->key) {
      x = x->left;
    } else if (k > x->key) {
      x = x->right;
    }
  }
  cout << "no" << endl;
}

void inorderBody(node *u) {
  if (u == NIL) return;
  inorderBody(u->left);
  cout << " " << u->key;
  inorderBody(u->right);
}

void inorder() {
  inorderBody(root);
  cout << endl;
}

void preorderBody(node *u) {
  if (u == NIL) return;
  cout << " " << u->key;
  preorderBody(u->left);
  preorderBody(u->right);
}

void preorder() {
  preorderBody(root);
  cout << endl;
}

int main() {
  int m, tmp;
  string s;
  root = NIL;
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> s;
    if (s == "insert") {
      cin >> tmp;
      insert(tmp);
    } else if (s == "print") {
      inorder();
      preorder();
    } else if (s == "find") {
      cin >> tmp;
      find(tmp);
    }
  }
}


Measured memory_bytes: 21908
//هوالحق
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int DLT = 1000000007;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> V(n + 1);
    for(int i = 0, x; i < m; i++){
        cin >> x;
        V[x] = -2;
    }
    V[0] = 1;
    if(V[1] == 0) V[1] = 1;
    for(int i = 2; i <= n; i++) if(V[i] == 0) V[i] = (max(0, V[i-1]) + max(0, V[i-2])) % DLT;
    cout << V[n];
}


Measured memory_bytes: 640
#include<iostream>
#include <algorithm>
#include <string>
#include<math.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << (a + b >= c ? "Yes" : "No") << endl;
    return 0;
}


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

typedef long double ld;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

template<typename has_less>
using ordered_set =
tree<has_less,
	null_type,
	less<has_less>,
	rb_tree_tag,
	tree_order_statistics_node_update>;
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define ALL(v) v.begin(),v.end()
#define fast_cin() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define lc (sidx * 2)
#define rc (lc + 1)

typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

bool bit(int n, int i) { return (n >> i) & 1; }
int ceil(int a, int b) { return ceil(((ld)a) / b); }

int faltu;

const int mod = 1e9+7;
const ll inf = 5e18;
const int N = 2e5 + 100;
const int LGN = 50;

int n, m, q;
vector <int> a(N), b;
ll curr[LGN];
ll cnt[LGN];
ll pw[N][LGN];

bool get_next(vector <int> &s, int alpha) {
	for(int i = s.size() - 1; i >= 0; i--) {
		if(s[i] < alpha) {
			s[i] ++;
			for(int j = i + 1; j < s.size(); j++) {
				s[j] = 1;
			}
			return true;
		}
	}
	return false;
}

int main()
{
	fast_cin();
	srand(time(0));

	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	bool flag = true;
	for(int i = 1; i < n; i++) {
		if(a[i] >= a[i + 1]) {
			flag = false;
		}
	}
	if(flag) {
		cout << 1 << endl;
	} else {
		for(int i = 1; i <= n; i++) {
			if(a[i] < LGN) {
				b.pb(a[i]);
			}
		}
		n = b.size();
		for(int i = 0; i < n; i++) {
			cnt[b[i]]++;
		}
		int lo = 2, hi = n, alpha, ans = 2;
		while(lo <= hi) {
			alpha = (lo + hi) >> 1;
			// int LGN = (log(n) / (log(alpha) * 1.0)) + 1;
			vector <int> s(b[0], 1);
			bool flag = true;
			for(int i = 1; i < n; i++) {
				if(b[i] <= LGN) {
					if(b[i] > b[i - 1]) {
						for(int j = 0; j < b[i] - b[i - 1]; j++) {
							s.pb(1);
						}
					} else if(b[i] == b[i - 1]){
						flag = get_next(s, alpha);
					} else {
						s.resize(b[i]);
						flag = get_next(s, alpha);
					}
				}
				if(!flag) {
					break;
				}
			}
			if(flag) {
				ans = alpha, hi = alpha - 1;
			} else {
				lo = alpha + 1;
			}
		}
		cout << ans << endl;
	}

	return 0;
}

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 2e6 + 5;




string s, t;
int n, m;

int nxt[maxn];
int indeg[maxn];
int dist[maxn];

bool start[maxn];

int pi[maxn];

void gen() {
    string S;
    while (int(S.length()) < n+m) {
	for (char c: s) {
	    S += c;
	}
    }
    S = t + "$" + S;
    int len = S.length();
    for (int i=1; i<len; i++) {
	int j=pi[i-1];
	while (j>0 && S[i]!=S[j]) {
	    j=pi[j-1];
	}
	if (S[i]==S[j]) j++;
	pi[i] = j;
    }

    for (int i=m; i<len; i++) {
	if (pi[i] == m) {
	    int idx = (i-(m+1))%n;
	    idx -= (m-1);
	    idx %= n;
	    idx += n;
	    idx %= n;
	    start[idx] = true;
	}
    }
}

void add_edge(int from, int to) {
    nxt[from] = to;
    indeg[to]++;
}


bool isroot(int i) {
    return start[i];
    // for (int j=0; j<m; j++) {
    // 	if (s[(i+j)%n] != t[j]) return false;
    // }
    // return true;
}

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

    cin>>s;
    cin>>t;
    n = s.length();
    m = t.length();

    gen();

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

    for (int i=0; i<n; i++) {
	if (isroot(i)) {
	    add_edge(i, (i+m)%n);
	}
    }


    queue<int> qq;
    for (int i=0; i<n; i++) {
	if (indeg[i]==0) {
	    qq.push(i);
	}
    }

    while (qq.size()) {
	int at = qq.front();
	qq.pop();
	int to = nxt[at];
	if (~to) {
	    dist[to] = max(dist[to], 1+dist[at]);
	    if (--indeg[to] == 0) {
		qq.push(to);
	    }
	}
    }

    for (int i=0; i<n; i++) {
	if (indeg[i]>0) out(-1); // cycle
    }

    int res = 0;
    for (int i=0; i<n; i++) {
	res = max(res, dist[i]);
    }

    cout<<res<<endl;    
    return 0;
}


Measured memory_bytes: 20468
#include<stdio.h>
#define INT_MAX 0x7f7f7f7f
struct EDGE
{
    int x, y, z;
}a[9905];
int v, e, dis[105][105];
int floyd()
{
    for(int i = 0; i < v; i++)
        for(int j = 0; j < v; j++)
            dis[i][j] = INT_MAX;
    for(int i = 1; i <= e; i++)
        dis[a[i].x][a[i].y] = a[i].z;

    for(int k =0; k < v; k++)
        for(int i = 0; i < v; i++){
            dis[i][i] = 0;
            for(int j = 0; j < v; j++)
                if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
                    if(dis[i][j] > dis[i][k] + dis[k][j])
                        dis[i][j] = dis[i][k] + dis[k][j];
            if(dis[i][i] < 0) return 0;
        }
    return 1;
}
int main()
{
    scanf("%d%d", &v, &e);
    for(int i = 1; i <= e; i++)
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
    if(floyd())
        for(int i = 0; i < v; i++)
            for(int j = 0; j < v; j++)
                if(dis[i][j] != INT_MAX) printf("%d", dis[i][j]), putchar(" \n"[j == v - 1]);
                else printf("INF"), putchar(" \n"[j == v - 1]);
    else printf("NEGATIVE CYCLE\n");
    return 0;
}


Measured memory_bytes: 2124
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int>d(N);
  for (int i = 0; i < N; i++) {
    cin >> d.at(i);
  }
  
  int count = 0;
  for (int i = 0; i < N-1; i++) {
    for (int j = i+1; j < N; j++) {
      count += d.at(i)*d.at(j);
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3592
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
string s;

int main() {
  INCANT;
  cin >> s;
  rep(i, s.size()) {
    char c = s[i]=='?'?'D':s[i];
    cout << c;
  }
  cout << endl;
  return 0;
}

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


int main(){
	int N, x;
	cin >> N >> x;
	vector<int> a(N);
	rep(i,N) cin >> a[i];
	sort(a.begin(),a.end());
	int ans = 0;
	rep(i,N) {
		x -= a[i];
		if(x<0){
			cout << ans << endl;
			return 0;
		}
		if(i == N-1&& x > 0){
			cout << ans << endl;
			return 0;
		}
		if(x==0){
			ans++;
			cout << ans << endl;
			return 0;
		}
		ans++;
	}
	

}













Measured memory_bytes: 3624
#include "iostream"
#include "string"
using namespace std;

long gcd(long a, long b)
{
  while (b != 0)
  {
    long i = a % b;
    a = b;
    b = i;
  }
  return a;
}

int main() {
  long n, m;
  cin >> n >> m;
  string s, t;
  cin >> s >> t;
  long g = gcd(n, m);
  long l = (n * m) / g;
  bool check = true;
  for (long i = 0; i < g; i++) {
    if (s[(i * n / g)] != t[(i * m / g)]) check = false;
  }
  cout << (check ? l : -1) << endl;
}

Measured memory_bytes: 512
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
uf = UnionFind(N)
XY = [list(map(int,input().split()))+[i] for i in range(N)]

X = sorted(XY, key=lambda i:i[0])
Y = sorted(XY, key=lambda i:i[1])

side = [[] for _ in range(len(X)+len(Y)-2)]
j = 0
for i in range(N-1):
  side[j] += [X[i+1][0]-X[i][0],X[i][2],X[i+1][2]]
  side[j+1] += [Y[i+1][1]-Y[i][1],Y[i][2],Y[i+1][2]]
  j += 2

ans = 0
side.sort()

for i,j,k in side:
  if uf.same(j,k):
    continue
  uf.union(j,k)
  ans += i

print(ans)

Measured memory_bytes: 130432
# 1が作れれば必ず終了できる
# 1が作れないようなやつはあるか？
# -> 6 18 26 31 40 があったとき、26と31だけで作れそう
# -> 偶奇が揃っていればいい？
# ex) ぜんぶ奇数だと奇数-奇数で偶数が作れるので結局いける？
# 21 29 45 うんいけそう(8を作れば5ができるので21%5=1)（16を作れば5がry）
# ただしサンプル曰くすべてが同じ数の倍数なら無理そう 適当に最初とそれ以外で試せばいいか
# と思ったけど[6 33 45]とかは作れないのでgcdをとって最後まで更新されなかったらアウトとする
# というか奇数だけでも偶数作れるから奇数さえあればいけるか

n, k = map(int, input().split())
arr = sorted(list(set(list(map(int, input().split())))))
n = len(arr)
if arr[0] == 1 or k in arr:
    print("POSSIBLE")
    exit()
if n < 2 or arr[-1] < k:
    print("IMPOSSIBLE")
    exit()


def gcd(a, b):
    if a > b:
        a, b = b, a
    while a > 0:
        a, b = b % a, a
    return b


tmp = gcd(arr[0], arr[1])
# あーもうめちゃくちゃだよ
if tmp == 1:
    print("POSSIBLE")
    exit()
flag = True
for i in range(2, n):
    g = gcd(tmp, arr[i])
    if g != tmp or g == 1:
        flag = False
        break
# あーもうめちゃくちゃだよ
if flag and k % tmp != 0:
    print("IMPOSSIBLE")
    exit()

even_flag, odd_flag = False, False
for a in arr:
    if a % 2 == 1:
        odd_flag = True
    else:
        even_flag = True

# あーもうめちゃくちゃだよ
if odd_flag:
    if k % 2 == 0 and not even_flag:
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")
    exit()

# あーもうめちゃくちゃだよ
if k % 2 == 1:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


Measured memory_bytes: 14480
#include <vector>
#include <cfloat>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <string>
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <cassert>
#include <random>
#include <queue>
#include <list>
#include <map>
#include <array>
#include <chrono>
 
using namespace std;

vector<pair<int,int> >red,blue;
map<int,int>used;

int main(){

	int i,j;

	int N;

	scanf("%d",&N);

	for(i=0;i<N;i++){
	int a,b;

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

	red.push_back(make_pair(a,b));

	}

	for(i=0;i<N;i++){
	int c,d;

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

	blue.push_back(make_pair(c,d));

	}

	sort(red.begin(),red.end());
	sort(blue.begin(),blue.end());

	int ans=0;

	for(i=0;i<N;i++){
		int x=blue[i].first;
		int y=blue[i].second;
		int rA=-1;
		int index=-1;
		for(j=0;j<N;j++){
			if(x>red[j].first&&y>red[j].second && used[j]==0){
			if(rA<red[j].second){
				rA=red[j].second;
				index=j;
			}
			}
		}
		if(index>=0){
		used[index]=1;
		ans++;
		}
	}
	printf("%d\n",ans);

return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// chmax, chmin
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;
}


struct Line {
    ll l;
    ll r;
    int id;

    ll size() {
        return max(0ll, r - l);
    }

    Line intersect(Line x) {
        return {max(x.l, l), min(x.r, r), -1};
    }

    bool contains(Line x) {
        return l <= x.l && x.r <= r;
    }
};


Line getMin(vector<Line> ps) {
    sort(ps.begin(), ps.end(), [](Line &a, Line &b) {
        if (a.r != b.r) {
            return a.r < b.r;
        }
    });
    return ps[0];
}

Line getMax(vector<Line> ps) {
    sort(ps.begin(), ps.end(), [](Line &a, Line &b) {
        return a.l > b.l;
    });
    return ps[0];
}


/*
 * 1 20
 * 2 19
 * 3 18
 * 4 17
 */
void solve(long long N, std::vector<long long> L, std::vector<long long> R) {
    vector<Line> ps;
    vector<long long> ls;
    for (int i = 0; i < N; i++) {
        ps.push_back({L[i], R[i] + 1, i});
        ls.push_back(L[i]);
    }

    sort(ls.begin(), ls.end());
    ls.erase(unique(ls.begin(), ls.end()), ls.end());

    ll ans = 0;
    for (auto i : ps) ans = max(ans, i.size());

    Line minL = getMin(ps);
    Line maxL = getMax(ps);


    int mindex = upper_bound(ls.begin(), ls.end(), minL.r) - ls.begin() - 1;

    Line tmp = maxL;
    bool used = false;

    vector<Line> A;
    multiset<ll> answer;

    for (int i = 0; i < N; i++) {
        if (i == minL.id || ps[i].contains({minL.r, minL.r})) {
            if (i != minL.id) answer.insert(ps[i].size());
            A.push_back(ps[i]);
        } else {
            tmp = tmp.intersect(ps[i]);
            used = true;
        }
    }

    auto app = [&](ll s) {
        if (!used) {
            ans = max(ans, *answer.rbegin() + Line{s, minL.r}.size());
        } else {
            ans = max(ans, tmp.size() + Line{s, minL.r}.size());
        }
    };

    app(minL.r);

    sort(A.begin(), A.end(), [&](Line &a, Line &b) {
        return a.l > b.l;
    });

    for (auto x : A) {
        app(x.l);
        int i = x.id;
        if (i != minL.id) answer.erase(answer.find(ps[i].size()));
        tmp = tmp.intersect(ps[i]);
        used = true;
    }
    cout << ans << endl;

}

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


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

typedef long long ll;

int main() {
  ll N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  ll diff = B - A;
  bool ans = false;
  // cout << diff << endl;
  for (ll i = 0; i <= N-1; i++) {
    ll l = (N-1 - i)*C - i*D;
    ll r = (N-1 - i)*D - i*C;
    // cout << l << " " << r << endl;
    if (l <= diff && diff <= r) ans = true;
  }
  cout << (ans ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
M, D = map(int, input().split())
ans = 0
for m in range(1, M+1):
    for d in range(1, D+1):
        d1 = d % 10
        d10 = d // 10
        if d1 >= 2 and d10 >= 2 and d1 * d10 == m:
            ans += 1
print(ans)


Measured memory_bytes: 39664
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;

int h, w;
int a[10][10];

bool answer = true;
void dfs(int x,int y)
{
	a[x][y] = 0;
	if (x == h - 1 && y == w - 1)return;
	bool nex1 = a[x + 1][y];
	bool nex2 = a[x][y + 1];
	if (nex1 ^ nex2)
	{
		if (nex1)
		{
			dfs(x + 1, y);
		}
		else
		{
			dfs(x, y + 1);
		}
	}
	else
	{
		answer = false;
		return;
	}
}

int main(void)
{
	scanf("%d %d", &h, &w);
	memset(a, 0, sizeof(a));
	for (int i = 0; i < h; ++i)
	{
		char s[10];
		scanf("%s", s);
		for (int j = 0; j < w; ++j)
		{
			a[i][j] = s[j] == '.' ? 0 : 1;
		}
	}
	dfs(0, 0);

	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			if (a[i][j] == 1)answer = false;
		}
	}
	if(answer)printf("Possible\n");
	else printf("Impossible\n");
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
long long int fie[4][1000003];
int main(){
    fie[0][0]=1;
    long long int N;
    long long int ans=1;
    cin>>N;
    for(int i=0;i<4;i++){
        for(int j=0;j<1000002;j++){
            fie[i][j]%=1000000007;
            if(i==0){
                fie[0][j+1]+=fie[0][j]*8;
                fie[1][j+1]+=fie[0][j];
                fie[2][j+1]+=fie[0][j];
            }
            else if(i==1){
                fie[1][j+1]+=fie[1][j]*9;
                fie[3][j+1]+=fie[1][j];
            }
            else if(i==2){
                fie[2][j+1]+=fie[2][j]*9;
                fie[3][j+1]+=fie[2][j];
            }
            else if(i==3){
                fie[3][j+1]+=fie[3][j]*10;
            }
        }
    }
    cout<<fie[3][N]%1000000007<<endl;
    return 0;
}


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


int main(){
  int a, b;
  char op;
  while(cin >> a >> op >> b){
    switch(op){
      case '+':
        cout << a+b << endl;
        break;
      case '-':
        cout << a-b << endl;
        break;
      case '*':
        cout << a*b << endl;
        break;
      case '/':
        cout << a/b << endl;
        break;
      case '?':
        return 0;
    }
  }

 return 0;
}

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

int main() {
	int A,B;
	cin >> A >> B;
	int ans = 0;
	ans += (B - 1) / (A - 1);
	if (0 != (B - 1) % (A - 1)) {
		ans++;
	}
	cout << ans <<endl;
	return 0;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> jobs(m);
    rep(i,n) {
        int a, b;
        cin >> a >> b;
        if(a>m) continue;
        jobs[m-a].push_back(b);
    }
    priority_queue<int> q;
    ll ans = 0;
    for(int i = m-1; i >= 0; --i) {
        for(int b : jobs[i]) q.push(b);
        if(!q.empty()) {
            ans += q.top();
            q.pop();
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5632
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    int array[3][3] = {0};
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> array[i][j];
        }
    }
    cin >> n;
    vector<int> tmp(n);

    for (int itmp = 0; itmp < n; itmp++) {
        cin >> tmp[itmp];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (array[i][j] == tmp[itmp]) {
                    array[i][j] = 0;
                }
            }
        }
    }

    if ((array[0][0] == array[0][1] && array[0][1] == array[0][2]) ||
        (array[1][0] == array[1][1] && array[1][1] == array[1][2]) ||
        (array[2][0] == array[2][1] && array[2][1] == array[2][2]) ||
        (array[0][0] == array[1][0] && array[1][0] == array[2][0]) ||
        (array[0][1] == array[1][1] && array[1][1] == array[2][1]) ||
        (array[0][2] == array[1][2] && array[1][2] == array[2][2]) ||
        (array[0][0] == array[1][1] && array[1][1] == array[2][2]) ||
        (array[0][2] == array[1][1] && array[1][1] == array[2][0]) 
        ) {
        cout << "Yes" << endl;
        return 0;
    }
    else {
        cout << "No" << endl;
        return 0;
    }
}

Measured memory_bytes: 384
#define _GLIBCXX_DEBUG
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<string>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rep2(i,s,n) for(int i=s;i< (int)n; i++)
#define ll long long 
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
  ll n,m;
  cin >>n>>m;
  vector<pair<ll,ll>> a(n);
  vector<pair<ll,ll>> c(m);
  vector<ll> ans(n);
  vector<ll> key(n);
  rep(i,n) cin >>a[i].first>>a[i].second;
  rep(i,m) cin >>c[i].first>>c[i].second;
  rep(i,n) ans[i]=0;
  rep(i,n) key[i]=abs(a[i].first-c[0].first)+abs(a[i].second-c[0].second);
  rep(i,n){
    rep(j,m-1){
      if(key[i]>abs(a[i].first-c[j+1].first)+abs(a[i].second-c[j+1].second)){
        key[i]=abs(a[i].first-c[j+1].first)+abs(a[i].second-c[j+1].second);
        ans[i]=j+1;
      }
    }
  }
         rep(i,n) cout <<ans[i]+1<<endl;
}

Measured memory_bytes: 256
main :: IO ()
main = do
    n <- readLn :: IO Int
    let ns = filter ((== 1) . (`mod` 5)) ps
    putStrLn $ unwords $ map show $ take n ns

ps :: [Int]
ps = 2 : f [3] [3, 5..]
    where
      f (x:xs) ys = let (ps, qs) = span (< x^2) ys
                    in ps ++ f (xs ++ ps) [z | z <- qs, z `mod` x /= 0]


Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

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

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int 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;
    }
}

// 二項係数計算
long long 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;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N; cin >> N;
    vector<int> f(70000,0);
    for(int i=1;i<=100;i++){
        for(int j=1;j<=100;j++){
            for(int k=1;k<=100;k++){
                int t = i*(i+j)+j*(j+k)+k*(k+i);
                f[t]++;
            }
        }
    }
    for(int i=0;i<N;i++){
        cout << f[i+1] << endl;
    }
    return 0;
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
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 long double PI = acos(-1.0);
// cout << fixed << setprecision(14);
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int D, T, S;
	cin >> D >> T >> S;
	if(S*T >= D) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 3648
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    cur=0
    ans=1
    for a in A:
        cur+=a
        if cur<=K:
            ans+=1
    print(ans)




if __name__ == "__main__":
    main()

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

typedef long long ll;
typedef pair<ll,ll> ii;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
const int INF=2012345678;
const ll LLINF=4012345678012345678LL;
const ll MOD=1000000007; //998244353; //
const ld PI=3.1415926535898;
const ld EPS=1e-9;
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(b==0)return a;return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll expo(ll b,ll p,ll m){ll res=1; while(p){if(p&1)res=(res*b)%m; b=(b*b)%m; p>>=1;} return res;}
inline ll modinv(ll a,ll m){return expo(a,m-2,m);}

int main(){
	int n;
	scanf("%d",&n);
	ll a[n],b[n];
	for(int i=0;i<n;i++)scanf("%lld%lld",&a[i],&b[i]);
	sort(a,a+n);sort(b,b+n);
	if(n%2==0){
		printf("%lld",1-a[n/2-1]-a[n/2]+b[n/2-1]+b[n/2]);
	}else{
		printf("%lld",1-a[n/2]+b[n/2]);
	}
}


Measured memory_bytes: 6992
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;} return false;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;} return false;}

int main(){
    int n;
    string s;
    cin >> n >> s;
    string tmp;
    int ans = 0;
    rep(i, 10){
        rep(k, 10){
            rep(m, 10){
                tmp = to_string(i);
                tmp += to_string(k);
                tmp += to_string(m);
                int cnt = 0;
                rep(j, n){
                    if(tmp.at(cnt) == s.at(j))
                    cnt++;
                    if(cnt == 3){
                        ans++;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <random>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n;
int a[200000];
int n2[200000];
int n5[200000];
int cnt[19][19];

signed main() {
	int i;
	
	cin >> n;
	rep(i, n) {
		double x;
		cin >> x;
		a[i] = x * (1e+9) + 0.1;
		
		int cnt2 = 0, tmp = a[i];
		while (tmp % 2 == 0) {
			tmp /= 2;
			cnt2++;
		}
		
		int cnt5 = 0;
		while (tmp % 5 == 0) {
			tmp /= 5;
			cnt5++;
		}
		
		cnt2 = min(cnt2, 18LL);
		cnt5 = min(cnt5, 18LL);
		n2[i] = cnt2;
		n5[i] = cnt5;
		cnt[cnt2][cnt5]++;
	}
	
	int res1 = 0;
	rep(i, n) {
		for (int j = 18 - n2[i]; j <= 18; j++) {
			for (int k = 18 - n5[i]; k <= 18; k++) {
				res1 += cnt[j][k];
			}
		}
	}
	
	int res2 = 0;
	rep(i, n) {
		if (n2[i] >= 9 && n5[i] >= 9) {
			res2++;
		}
	}
	
	cout << (res1 - res2) / 2 << endl;
	return 0;
}

Measured memory_bytes: 8328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
/* ちゃんと考えてわかって実装 */

const int MAX_V = 50;
const int MAX_S = 50 * MAX_V + 5;
const ll INF = 1e18;

struct Edge{
    int to, a, b;

    // これを書いたらerrorが取れた。どうして必要なのｫぉ
    Edge(int to, int a, int b):to(to),a(a),b(b) {}
};

struct State{
    int v, s; // state = (頂点, 所持金)
    ll x; // その状態までの経過時間

    // これを書いたらerrorが取れた。どうして必要なのｫぉ
    State(int v, int s, ll x):v(v),s(s),x(x) {}

    bool operator<(const State& a) const {
        return x > a.x; // (x < a.x だとちゃんと動かねぇ)
    }
};

vector<Edge> g[MAX_V]; // 各頂点から伸びている辺の集合として保持。
ll min_time[MAX_V][MAX_S+5]; // 状態(v, s)までの最小の時間を記録。


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

    for(int i=0; i<m; i++){
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--; v--;
        g[u].emplace_back(v, a, b);
        g[v].emplace_back(u, a, b);
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<MAX_S+5; j++){
            min_time[i][j] = INF;
        }
    }

    vector<int> c(n), d(n);
    for(int i=0; i<n; i++){
        cin >> c[i] >> d[i];
    }

    s = min(s, MAX_S); // 十分な値で切り捨てる。
    priority_queue<State> pq;

    // pqに状態(v, s, x)を emplace するときに、
    // min_time[v][s]の値を x に更新する。(xが最小じゃないなら更新しない。)
    auto push = [&](int v, int s, ll x){
        if(s < 0) return;
        if(min_time[v][s] <= x) return;
        min_time[v][s] = x;
        pq.emplace(v, s, x);
    };
    // 初期状態は(0, s, 0)
    push(0, s, 0);
    while(!pq.empty()){
        State now = pq.top(); pq.pop();
        int v = now.v, s = now.s;
        ll x = now.x;
        if(min_time[v][s] != x) continue; // なぜ?????
        {
            // 遷移その1 : 換金
            int next_s = min(s+c[v], MAX_S);
            push(v, next_s, x+d[v]);
        }

        // 遷移その2 : 電車に乗る
        // そこから伸びている辺を全てみる
        for(Edge e : g[v]){
            push(e.to, s-e.a, x+e.b);
        }
    }

    for(int i=1; i<n; i++){
        ll ans = INF;
        for(int j=0; j<MAX_S+5; j++){
            ans = min(ans, min_time[i][j]);
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 6232
from collections import deque
n = int(input())
v = list(map(int,input().split()))
v.sort(reverse=True)
stack = deque()
for i in v:
    stack.append(i)
while stack:
    if len(stack) == 1:
        print(stack.pop())
    else:
        small1 = stack.pop()
        small2 = stack.pop()
        tmp = (small1 + small2)/2
        stack.append(tmp)

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

const int MOD = 1e9 + 7;

int main(int argc, char const *argv[])
{
	int n, m; cin >> n >> m;
	vector<int> a(m); rep(i, m) cin >> a[i];
	set<int> st; rep(i, m) st.insert(a[i]);

	vector<int> dp(n + 1);
	dp[0] = 1;
	rep(i, n) {
		rep(j, 2) {
			int add = j + 1;
			if (i + add > n) continue;
			if (st.count(i + add)) continue;
			(dp[i + add] += dp[i]) %= MOD;
		}
	}
	printf("%d\n", dp[n]);

	return 0;
}


Measured memory_bytes: 5760