akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
template <class T> using V = vector<T>;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(ll)(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
ll combi(ll n,ll m) {
  ll ans=1;
  rFOR(i,n,n-m){
    ans*=i;
  }
  FOR(i,1,m+1){
    ans/=i;
  }
  return ans;
}
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}



/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll n,m;
  	ci(n>>m);
  vll A(100000);
  ll ans=0;
  FOR(i,10000,100000){
    ll a=i;
    if(a%10==a/10000){
     
	a/=10;
    a=a%1000;
      
    if(a%10==a/100){
      ans++;
    }
    }
    A[i]=ans;
  }
  co(A[m]-A[n-1]);
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <math.h>
#include <map>
#include <vector>
using namespace std;

int main() {
	int h, w, d;
	cin >> h >> w >> d;
	int a;
	int px[90000], py[90000], count[90000] = {};
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> a;
			px[a] = i;
			py[a] = j;
		}
	}
	long long q;
	cin >> q;
	for (int i = d + 1; i <= h*w; i++) {
		count[i] = count[i - d] + abs(px[i] - px[i - d]) + abs(py[i] - py[i - d]);
	}
	int l, r;
	for (long long i = 0; i < q; i++) {
		cin >> l >> r;
		cout << count[r] - count[l] << endl;
	}

	return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
int d[1001],c[1001];
int n,m;
int memo[1001][1001];
int solve(int day,int tosi){
  if(tosi==n){
    return 0;
  }
  if(day==m){
    return 1000000000;
  }
  if(memo[day][tosi]) return memo[day][tosi];
  int ret=0;
  ret+=min(solve(day+1,tosi+1)+d[tosi]*c[day] , solve(day+1,tosi) );
  return memo[day][tosi]=ret;
}
int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    cin>>d[i];
  }
  for(int i=0;i<m;i++){
    cin>>c[i];
  }

  cout<<solve(0,0)<<endl;
}
  

Measured memory_bytes: 5140
#include <iostream>
#include <cmath>
#include <iomanip>
int main() {
    double x1, y1, x2, y2;
    std::cin >> x1 >> y1 >> x2 >> y2;
    std::cout << std::fixed << std::setprecision(6)
        << std::sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
        << std::endl;
}



Measured memory_bytes: 3260
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>

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

int main() {

	ll N, M;

	scanf("%lld %lld", &N, &M);

	if (N == 1 && M == 1) {
		printf("1\n");
		return 0;
	}

	if (N == 1) {
		printf("%lld\n", M - 2);
		return 0;
	}
	if (M == 1) {
		printf("%lld\n", N - 2);
		return 0;
	}


	printf("%lld\n", (N - 2)*(M - 2));

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using namespace std;
using namespace atcoder;
using mint = modint1000000007;
int op(int a, int b) { return max(a, b); }

int e() { return 0; }

int target;

bool f(int v) { return v < target; }


int main() {
    int n,k;cin>>n>>k;
    vector<int> a(n);
    rep(i,n)cin>>a[i];
    segtree<int,op,e> seg(300005);
    target=k;
    seg.set(a[0],1);
    for(int i=1;i<n;i++){
        seg.set(a[i],seg.prod(max(a[i]-k,0),min(a[i]+k+1,300005))+1);
    }
    cout<<seg.prod(0,300005)<<endl;
}

Measured memory_bytes: 9588
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main() {FIN
    
    int h, n, m, hs;
    string w;
    while (cin >> w, w != "-") {
        cin >> m;
        hs = 0;
        n = w.size();
        while (m--) {
            cin >> h;
            hs += h;
        }
        h = (hs % n);
        cout << w.substr(h) + w.substr(0, h) << "\n";
    }
    
    return 0;
}



Measured memory_bytes: 3212
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(m)]
ans = 0
for i in edge:
    l = list(range(n))
    for j in edge:
        if j != i:
            l = [l[j[0] - 1] if l[k] == l[j[1] - 1] else l[k] for k in range(n)]
    if len(set(l)) != 1:
        ans += 1
print(ans)

Measured memory_bytes: 3064
def use_fast_io():
    global input
    import io
    import sys
    f = io.BytesIO(sys.stdin.buffer.read())
    input = f.readline
use_fast_io()


from scipy.sparse.csgraph import floyd_warshall
import numpy as np

N, M, L = map(int, input().split())
graph = np.zeros((N, N), dtype=int)
for _ in range(M):
    s, t, w = map(int, input().split())
    if w <= L:
        graph[s-1, t-1] = graph[t-1, s-1] = w
graph = floyd_warshall(graph, directed=False)
graph = floyd_warshall(graph <= L, directed=False)
graph[np.isinf(graph)] = 0

Q = int(input())
ans = []
for _ in range(Q):
    s, t = map(int, input().split())
    ans.append(int(graph[s-1][t-1]) - 1)
print(*ans, sep='\n')


Measured memory_bytes: 19616
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var HW = ReadLine().Split().Select(int.Parse).ToArray();
        var H = HW[0];
        var W = HW[1];
        var x = new UnionFind[H];
        for (int i = 0; i < H; i++)
        {
            x[i] = new UnionFind(W);
        }
        var y = new UnionFind[W];
        for (int i = 0; i < W; i++)
        {
            y[i] = new UnionFind(H);
        }

        var m = new bool[H, W];
        for (int i = 0; i < H; i++)
        {
            var S = ReadLine();
            for (int j = 0; j < W; j++)
            {
                m[i, j] = S[j] == '.';
            }
        }

        for (int i = 0; i < H; i++)
        {
            for (int j = 1; j < W; j++)
            {
                if (m[i, j - 1] && m[i, j]) x[i].Unite(j - 1, j);
            }
        }

        for (int i = 1; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                if (m[i - 1, j] && m[i, j]) y[j].Unite(i - 1, i);
            }
        }

        var ans = 0;
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                ans = Max(ans, x[i].Size(j) + y[j].Size(i) - 1);
            }
        }
        WriteLine(ans);
    }
}

public class UnionFind
{
    int[] parent;
    int count;
    public int Count => count;

    public UnionFind(int length)
    {
        parent = new int[length];
        for (int i = 0; i < parent.Length; i++)
        {
            parent[i] = -1;
        }
        count = length;
    }

    int Root(int x) => parent[x] < 0 ? x : parent[x] = Root(parent[x]);

    public bool Same(int x, int y) => Root(x) == Root(y);

    public void Unite(int x, int y)
    {
        x = Root(x);
        y = Root(y);
        if (x == y) return;
        count--;
        if (parent[x] < parent[y])
        {
            parent[x] += parent[y];
            parent[y] = x;
        }
        else
        {
            parent[y] += parent[x];
            parent[x] = y;
        }
    }

    public int Size(int x) => -parent[Root(x)];
}


Measured memory_bytes: 53580
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main (){
  int N,M;
  cin >> N >> M ;
  int a[M];
  int b[M];
  for (int i=0; i<M;i++){
    cin >> a[i] >> b[i];
  }
  map<int, int> mp;
  for (int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      if(i+1==a[j]||i+1==b[j]){mp[i]++;}
    }
    cout << mp[i] << endl;
  }
}



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

namespace AtCoder
{
    static class Solver
    {
        static IO io = new IO();

        public static void Solve()
        {
            io.ReadSplit();
            int x = io.Int();
            int y = io.Int();

            string str = "ACABABAABABA";

            if (str[x - 1] == str[y - 1])
            {
                io.WriteLine("Yes");
            }
            else
            {
                io.WriteLine("No");
            }
        }
    }
}
namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            Solver.Solve();
        }
    }
    class IO
    {
        private string[] _Inputs;
        private int _Index;
        public void Read()
        {
            _Inputs = new string[1];
            _Inputs[0] = Console.ReadLine();
            _Index = 0;
        }
        public void ReadSplit()
        {
            _Inputs = Console.ReadLine().Split(' ');
            _Index = 0;
        }
        public string String()
        {
            return _Inputs[_Index++];
        }
        public string[] String(int xCount)
        {
            string[] rv = new string[xCount];
            Array.Copy(_Inputs, _Index, rv, 0, xCount);
            _Index += xCount;
            return rv;
        }
        public int Int()
        {
            return int.Parse(_Inputs[_Index++]);
        }
        public int[] Int(int xCount)
        {
            int[] rv = new int[xCount];
            for (int i = 0; i < xCount; ++i)
            {
                rv[i] = int.Parse(_Inputs[_Index++]);
            }
            return rv;
        }
        public long Long()
        {
            return long.Parse(_Inputs[_Index++]);
        }
        public long[] Long(int xCount)
        {
            long[] rv = new long[xCount];
            for (int i = 0; i < xCount; ++i)
            {
                rv[i] = long.Parse(_Inputs[_Index++]);
            }
            return rv;
        }
        public void Write(string xStr)
        {
            Console.Write(xStr);
        }
        public void WriteLine(string xStr)
        {
            Console.WriteLine(xStr);
        }
    }
}

Measured memory_bytes: 11092
s = str(input())
w1,w2,b1,b2 = 0,0,0,0
for i in range(len(s)):
  if i % 2 == 0:
    if s[i] == "0":
      w1 += 1
    else:
      b1 += 1
  else:
    if s[i] == "0":
      w2 += 1
    else:
      b2 += 1
print(min(w1+b2,w2+b1))


Measured memory_bytes: 3188
import fractions
a,b,c,d = map(int,input().split())
e,f,g = (a-1)//c,(a-1)//d,(a-1)//(c * d // fractions.gcd(c, d))
h,i,j = b//c,b//d,b//(c * d // fractions.gcd(c, d))
ans = (b-a+1)-((h+i-j)-(e+f-g))
print(ans)

Measured memory_bytes: 5048
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std;
using lint = long long;
using ld = long double;

int main(void) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    
    int dx = x2 - x1;
    int dy = y2 - y1;
    int x3 = x2 + (-dy);
    int y3 = y2 + (+dx);
    int x4 = x1 + (-dy);
    int y4 = y1 + (+dx);
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
}

Measured memory_bytes: 256
program speedrun
   implicit none
   character(10)::S,T,U
   integer::a,b
   read*,S,T
   read*,a,b
   read*,U
   if(S==U)a=a-1
   if(T==U)b=b-1
   print"(i0,A,i0)",a," ",b
end program speedrun


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

//=============warshall_floyd============================
vector<vector<long long>>  warshall_floyd(long long V, vector<vector<long long>> d)
{
  for (long long k = 0; k < V; ++k)
  {
    for (long long i = 0; i < V; ++i)
    {
      for (long long j = 0; j < V; ++j)
      {
        if (d[i][k] == INF || d[k][j] == INF)
        {
          continue;
        }
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
  return d;
}
//=================================================

int main()
{
  long long V, E;
  cin >> V >> E;
  long long s, t, d;
  vector<vector<long long>> dist(V, vector<long long>(V, INF));
  for (long long i = 0; i < V; ++i)
  {
    dist.at(i).at(i) = 0;
  }
  for (long long i = 0; i < E; ++i)
  {
    cin >> s >> t >> d;
    dist.at(s).at(t) = d;
  }
  dist = warshall_floyd(V, dist);
  for (long long i = 0; i < V; ++i)
  {
    if (dist.at(i).at(i) < 0)
    {
      cout << "NEGATIVE CYCLE" << endl;
      return 0;
    }
  }
  for (long long i = 0; i < V; ++i)
  {
    for (long long j = 0; j < V; ++j)
    {
      if (j)
      {
        cout << " ";
      }
      if (dist.at(i).at(j) == INF)
      {
        cout << "INF";
      }
      else
      {
        cout << dist.at(i).at(j);
      }
    }
    cout << endl;
  }
}



Measured memory_bytes: 3296
#include<stdio.h>
int main(){
  int r;
  scanf("%d",&r);
  if(r<1200){
    printf("ABC");
  }
  else if(r>=1200 && r<2800){
    printf("ARC");
  }
  else{
    printf("AGC");
  }
  
  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[]a = new int[n];

    double all = 0;
    for(int i=0; i<n; i++) {
    	a[i] = sc.nextInt();
    	all += (double)1.0/a[i];
    }   	
     	System.out.println(1.0/all);
    }
}

Measured memory_bytes: 35920
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

int d[5];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	for (int i = 0; i < 3; ++i) {
		int u, v;
		cin >> u >> v;
		++d[u];
		++d[v];
	}

	for (int i = 1; i <= 4; ++i)
		if (d[i] > 2) {
			cout << "NO" << endl;
			return 0;
		}

	cout << "YES" << endl;	

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
ll INF = (1LL << 60) - 1;
int MOD = 1e9+7;
int calc(ll x){
    int res = 0;
    while(x > 0){
        res += x % 10;
        x /= 10;
    }
    return res;
}
string to_str(ll A){
    stringstream ss;
    ss << A;
    return ss.str();
}
ll next(ll x){
    vector<ll> cand;
    cand.push_back(x);
    ll d = 10;
    rep(i,0,15){
        cand.push_back(d * (x / d + 1) - 1);
        //if(d > x * 10)break;
        d *= 10;
    }
    double mini = 1e16;
    ll ans;
    for(auto i:cand){
        //cout << i << " ";
        if(mini > 1. * i / calc(i)){
            mini = 1. * i / calc(i);
            ans = i; 
        }
    }
    //cout << endl;
    return ans;
}
main(){
    int K;
    cin >> K;   
    ll x = 1;
    rep(i,0,K){
        cout << x << endl;
        x = next(x+1);
    }
}

Measured memory_bytes: 256
#include <stdio.h>
int num[100000];

int main(void)
{
  int i, s, x;

  scanf("%d", &x);

  for(i = 0; i < 100000; i++)
    num[i] = ((i+1)*(i+2))/2;

  for(i = 0; i < 100000; i++){
    if(x <= num[i]){
      printf("%d\n", i+1);
      break;
    }
  }
  return 0;
}


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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
// const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}


int main() {
  int64 K;
  cin >> K;
  auto X = divisor(K - 1);
  auto Y = divisor(K);
  for(auto &p : Y) X.emplace_back(p);
  sort(begin(X), end(X));
  X.erase(unique(begin(X), end(X)), end(X));
  int64 ret = 0;
  auto get = MFP([&](auto get, int64 X, int64 p) -> bool {
    if(X < p) {
      return X == 1;
    }
    if(X % p == 0) {
      X /= p;
      return get(X, p);
    }
    if(X - p < p) return get(X - p, p);
    X -= (X / p - 1) * p;
    return get(X, p);
  });
  for(auto &p : X) {
    if(p == 1) continue;
    ret += get(K, p);
  }
  cout << ret << endl;
}






Measured memory_bytes: 384
a=[0]*26
w='abcdefghijklmnopqrstuvwxyz'
try:
    while True:
        s=list(input().upper())
        for i in s:
            if i=='A':
                a[0]+=1
            elif i=='B':
                a[1]+=1
            elif i=='C':
                a[2]+=1
            elif i=='D':
                a[3]+=1
            elif i=='E':
                a[4]+=1
            elif i=='F':
                a[5]+=1
            elif i=='G':
                a[6]+=1
            elif i=='H':
                a[7]+=1
            elif i=='I':
                a[8]+=1
            elif i=='J':
                a[9]+=1
            elif i=='K':
                a[10]+=1
            elif i=='L':
                a[11]+=1
            elif i=='M':
                a[12]+=1
            elif i=='N':
                a[13]+=1
            elif i=='O':
                a[14]+=1
            elif i=='P':
                a[15]+=1
            elif i=='Q':
                a[16]+=1
            elif i=='R':
                a[17]+=1
            elif i=='S':
                a[18]+=1
            elif i=='T':
                a[19]+=1
            elif i=='U':
                a[20]+=1
            elif i=='V':
                a[21]+=1
            elif i=='W':
                a[22]+=1
            elif i=='X':
                a[23]+=1
            elif i=='Y':
                a[24]+=1
            elif i=='Z':
                a[25]+=1 

except EOFError:
    pass

for i in range(26):
    print(w[i:i+1], ':', str(a[i]))

Measured memory_bytes: 7532
#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);
    cout << fixed << setprecision(12);


    int H, W;
    cin >> H >> W;
    const int A = 10;
    vector<vector<int>> M(A, vector<int>(A, 0));

    for (int i = 0; i < A; ++i) {
        for (int j = 0; j < A; ++j) {
            cin >> M[i][j];
        }
    }

    for (int k = 0; k < A; ++k) {
        for (int i = 0; i < A; ++i) {
            for (int j = 0; j < A; ++j) {
                M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
            }
        }
    }

    long long res = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            int x;
            cin >> x;
            if (x >= 0) {
                res += M[x][1];
            }
        }
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 3596
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	int n;
	char s[];
	public void run() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		s = sc.next().toCharArray();
		int x[] = new int[n+1];
		int min = 0;
		String ans ="";
		for(int i=0; i<n; i++) {
			if(s[i]=='(') {
				x[i+1]=x[i]+1;
			}else {
				x[i+1]=x[i]-1;
			}
			min = Math.min(min, x[i+1]);
			ans += s[i];
		}
		while(min<0) {
			ans = "("+ans;
			x[n]++;
			min++;
		}
		while(x[n]>0) {
			ans = ans + ")";
			x[n]--;
		}
		System.out.println(ans);
		sc.close();
	}


}




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

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

	if ((x == 3) || (x == 5) || (x == 7)) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
/*
title:

url:
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <queue>
#include <limits>
#include <string>
#include <utility>
#include <cstring>
#include <map>
#include <cmath>
#include <iterator>

using namespace std;

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

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

int main()
{
    int n = 0;
    cin >> n;
    int a[n];
    REP(i, n)
    {
        cin >> a[i];
    }
    sort(a, a + n, greater<int>());
    int alice = 0, bob = 0;
    REP(i, n)
    {
        if (i % 2 == 0)
            alice += a[i];
        else
            bob += a[i];
    }
    cout << alice - bob << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.IO.Compression;
using System.IO.Pipes;
using System.Linq;
using System.Numerics;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var pmc = ReadInts();
            WriteLine(pmc.Sum());
        }
        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}



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

int main() {
    int r, d, x;
    cin >> r >> d >> x;
    for(int i = 0; i < 10; i++) {
        cout << r*x-d << endl;
        x = r*x-d;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define e "\n"
#define MaRiaMa { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
#define fix(n) cout << fixed << setprecision(n);
using namespace std;
int main()
{
	MaRiaMa;
	int x, y, z;
	cin >> x >> y >> z;
	x -= z;
	cout<<int(x / (y + z));
}

Measured memory_bytes: 3624
get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n', '', _, String).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2)

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).
*/

f([A,A,B,C]).
f([A,B,B,C]).
f([A,B,C,C]).

main :-
    get_string(S),
    string_chars(S, S2),
    (f(S2)) -> writeln("Bad") ; writeln("Good").


Measured memory_bytes: 8012
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using psi=pair<string,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void get(){}template<class H,class...T>void get(H&h,T&...t){cin>>h;get(t...);}
template<class T>void geti(T&a){for(auto&_:a)cin>>_;}
template<class T>void getii(T&a){for(auto&_:a)geti(_);}
void put(string d){}template<class H,class...T>void put(string d,H&h,T&...t){cout<<h;if(sizeof...(t))cout<<d;put(d,t...);}
template<class T>void puti(T&a,string d=" "){bool f=1;for(auto&_:a)cout<<(exchange(f,0)?"":d)<<_;cout<<endl;}
template<class T>void putii(T&a,string d=" "){for(auto&_:a)puti(_,d);}
#define dcl(...) ll __VA_ARGS__;get(__VA_ARGS__)
#define dclt(t,...) t __VA_ARGS__;get(__VA_ARGS__)

 
constexpr int gcd(int a,int b){return b?gcd(b,a%b):a;}
constexpr int lcm(int a,int b){return a*b/gcd(a,b);}


int main(){
    dcl(n,x);
    deque<ll> a(n+2,0);
    ll ans=0;
    range(i,1,n+1){
        cin>>a[i];
    }
    range(i,1,n+1){
        if(a[i-1]+a[i]>x && a[i]+a[i+1]>x){
            ll d=min(a[i-1]+a[i],a[i]+a[i+1])-x;
            ans+=d;
            a[i]-=d;
        }
    }
    range(i,1,n){
        ans+=max(a[i]+a[i+1]-x,0ll);
    }
    cout<<ans<<endl;
}


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

int main(){
    int D, G;
    cin >> D >> G;
    vector<int> p(D), c(D);
    rep(i, D) cin >> p[i] >> c[i];
    vector<int> a;
    for (int bit = 0; bit < (1<<D); bit++){
        int score = 0;
        int sum = 0;
        for (int i = 0; i < D; i++){
            if (bit & (1<<i)){
                score += 100*(i+1)*p[i] + c[i];
                sum += p[i];
            }
        }
        if (score >= G){
            a.push_back(sum);
        }else {
            for (int i = D - 1; i >= 0; i--){
                if (!(bit&(1<<i))){
                    for (int j = 0; j < p[i] - 1; j++){
                        score += 100*(i+1);
                        sum++;
                        if (score >= G){
                            a.push_back(sum);
                            break;
                        }
                    }
                }
            }
        }
    }

    sort(ALL(a));
    cout << a[0] << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
 
#define MAX 100000
 
void swap(int*,int*);
void Partition(int,int,int*);
 
int main(){
  int n,i,A[MAX];
  scanf("%d",&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d",&A[i]);
  }
  Partition(0,n-1,A);
  return 0;
}
 
void swap(int *a,int *b){
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
 
void Partition(int l,int r,int *A){
  int x = A[r],i = l,j;
  for(j = l ; j < r ; j++){
    if(A[j] <= x){
      swap(&A[i++],&A[j]);
    }
  }
  swap(&A[i],&A[r]);
  for(j = l ; j <= r ; j++){
    if(j > l){ printf(" "); }
    if(j == i){
      printf("[%d]",A[j]);
    }else{
      printf("%d",A[j]);
    }
  }
  printf("\n");
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define LL long long
#define N 250010
using namespace std;

const int mo = 1000000007;

int n,m,tme,e=1,k,ve,top,max_dep;
int first[N],vfirst[N],d[N],h[N];
int dfn[N],st[N],vis[N];
LL g[N][2],pw[N],ans;
int f[N][21];
LL a[N],PRE[N],NXT[N];
std::vector<int> V[N];

struct edge {int v, next;} s[2 * N], vs[2 * N];
void add(int u, int v)
{
    s[e].next=first[u]; s[e].v=v; first[u]=e++;
    s[e].next=first[v]; s[e].v=u; first[v]=e++;
}
void addv(int u, int v)
{
    vs[ve].next=vfirst[u]; vs[ve].v=v; vfirst[u]=ve++;
}

void dfs(int u, int fa) 
{
    d[u]=d[fa]+1; max_dep=max(max_dep, d[u]); V[d[u]].push_back(u);
    f[u][0]=fa; dfn[u]=++tme;
    for (int e=first[u]; e; e=s[e].next) {
        int v=s[e].v;
        if (v==fa) continue;
        dfs(v, u);
    }
}

int cmp(const int& a, const int& b) {return dfn[a] < dfn[b];}

void pre() 
{
    for (int i=1; i<=20; i++)
        for (int j=1; j<=n; j++) 
            f[j][i]=f[f[j][i-1]][i-1];
}

int LCA(int x, int y) 
{
    if (d[x]<d[y]) swap(x, y);
    for (int i=20; i >= 0; i--)
        if (d[f[x][i]] >= d[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = 20; i >= 0; i--)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

void dp(int u) 
{
    LL ALL = 1;
    if (!vfirst[u]) 
    {
        g[u][0] = 1;
        g[u][1] = 1;
        return;
    } else {g[u][0] = g[u][1] = 0;}
    for (int e = vfirst[u]; e; e = vs[e].next) 
    {
        int v = vs[e].v; dp(v);
        ALL = ALL * ((g[v][0] + g[v][1]) % mo) % mo;
    }
    int num = 0;
    for (int e = vfirst[u]; e; e = vs[e].next) 
    {
        int v = vs[e].v;
        a[++num] = g[v][0];
    }

    PRE[0] = NXT[num + 1] = 1;
    for (int i = 1; i <= num; i++) PRE[i] = PRE[i - 1] * a[i] % mo;
    for (int i = num; i; i--) NXT[i] = NXT[i + 1] * a[i] % mo;
    for (int e = vfirst[u], t = 0; e; e = vs[e].next) 
    {
        int v = vs[e].v; t++;
        (g[u][1] += PRE[t - 1] * NXT[t + 1] % mo * g[v][1] % mo) %= mo;
    }
    g[u][0] = (ALL - g[u][1]) % mo;
    vfirst[u] = 0;
}

void solve(int D) 
{
    top = 0; ve = 1;
    k = V[D].size();
    for (int i=0; i<V[D].size(); i++) h[i + 1] = V[D][i]; h[++k] = 1;
    sort(h + 1, h + k + 1, cmp); st[++top] = 1;
    for (int i = 1; i <= k; i++) 
    {
        int x = h[i], lca = LCA(st[top], x);
        while (dfn[lca] < dfn[st[top]]) 
        {
            if (dfn[st[top - 1]] <= dfn[lca]) 
            {
                addv(lca, st[top--]);
                if (st[top] != lca) st[++top] = lca;
                break;
            }
            addv(st[top - 1], st[top]); top--;
        }
        if (st[top] != x) st[++top] = x;
    }
    while (top >= 2) addv(st[top - 1], st[top]), top--;
    dp(1); (ans += pw[n - V[D].size()] * g[1][1] % mo) %= mo;
}

int main() 
{
    scanf("%d",&n);
    pw[0] = 1;
    for (int i = 1; i <= n + 1; i++) pw[i] = pw[i - 1] * 2 % mo; n++;
    for (int i = 2, u, v; i <= n; i++) 
    {
        u = i, scanf("%d",&v); v++; add(u, v);
    }
    dfs(1, 0); pre();
    for (int i = 1; i <= max_dep; i++) 
        solve(i);
    printf("%lld\n", (ans + mo) % mo);
    return 0;
}

Measured memory_bytes: 63744
#include<iostream>
#include<cstdio>
#include<cmath>
#define neko 300010
#define mid ((l+r+1)>>1)
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register long long i=(a);i<=(b);i=-(~i))
#define rf(i,a,b) for(register long long i=(a);i>=(b);i=~(-i))
long long n,x,y,l,r;
using namespace std;
long long qrank(long long x,long long y){return y>=x?y+1:y;}
bool check(long long sum)
{
	long long chk=sum/2;
	f(i,chk-200,chk+200)
		if(i>0&&i<=sum)if(qrank(x,i)*qrank(y,sum-i+1)>=x*y)return 0;
	return 1;
}
signed main()
{
	scanf("%lld",&n);
	f(i,1,n)
	{
		scanf("%lld%lld",&x,&y);
		l=0,r=2e9;
		while(l<r)
		{
			if (check(mid))l=mid;else r=mid-1;
		}printf("%lld\n",l);
	}return 0;
}


Measured memory_bytes: 256
n = int(input())
l = [[0, 0] for _ in range(n)]
ans = "Yes"
for i in range(n):
    a, b = map(int, input().split())
    l[i][0] = b
    l[i][1] = a
l.sort()
t = 0
for i in range(n):
    t += l[i][1]
    if t > l[i][0]:
        ans = "No"
        break
print(ans)


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

int main()
{
    string a, b;
    cin >> a >> b;
    int x = stoi(a + b);
    bool ans = false;
    for(int i = 0; i * i <= x ; i++){
        if(i * i == x){
            ans = true;
            break;
        } 
    }

    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repR(i, n) for(int i = (n) - 1; i > -1; i--)
#define rep1(i, n) for(int i = 1; i < (int)(n + 1); i++)
#define rep1R(i, n) for(int i = (n); i > 0; i--)
using namespace std;

int F[50] = {};

int fibonacci(int n) {
  if (n == 0 || n == 1) return F[n] = 1;
  if (F[n] != 0) return F[n];
  return F[n] = fibonacci(n - 2) + fibonacci(n - 1);
}

int main() {
  int N;
  cin >> N;
  cout << fibonacci(N) << endl;
  return 0;
}



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

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
const double EPS=1e-6;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int)((a).size())
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) a.rbegin(),a.rend()
#define FLL(a,b) memset((a),b,sizeof(a))
#define CLR(a) FLL(a,0)
#define declare(a,it) __typeof(a) it=(a)
#define FOR(it,a) for(declare(a.begin(),it);it!=a.end();++it)
#define FORR(it,a) for(declare(a.rbegin(),it);it!=a.rend();++it)
template<class T,class U> ostream& operator<< (ostream& o, const pair<T,U>& v){return o << "(" << v.F << ", " << v.S << ")";}
template<class T> ostream& operator<< (ostream& o, const vector<T>& v){o << "{";rep(i,SZ(v)) o << (i?", ":"") << v[i];return o << "}";}
int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,-1,1,1,-1};
int s2i(string& a){stringstream ss(a);int r;ss>>r;return r;}
int geti(){int n;scanf("%d", &n);return n;}

string in[110];
bool vis[110][110][4][12][12];


int main(){
  int n,m,a;
  cin >> n >> m >> a;
  for(int i = 0; i < n; ++i)
    cin >> in[i];
  struct state{
    int cx,cy,dir,p,q;
    state(int _x,int _y, int _d, int _p, int _q):
      cx(_x),cy(_y),dir(_d),p(_p),q(_q)
    {}
  };
  
  queue<state> Q;
  for(int i = 0; i + 1 < n; ++i)
    for(int j = 0; j < m; ++j)
      if(in[i][j] == 'S')
        Q.push(state(i+1,j,1,a,a));

  int ans = 1000000;
  
  while(!Q.empty()){
    state cst = Q.front();Q.pop();
    int cx = cst.cx;
    int cy = cst.cy;
    int di = cst.dir;
    int p = cst.p;
    int q = cst.q;
    if(vis[cx][cy][di][p][q]) continue;
    vis[cx][cy][di][p][q] = 1;
    //cout << cx << " "  << cy << " " << di << " " << p << " " << q << endl;
    if(in[cx][cy] == 'S' && di==3) continue;
    if(in[cx][cy] == '#') continue;    
    if(in[cx][cy] == 'G')
      ans = min(ans, 2*a-(p+q));
    
    {
      int nx = cx + dx[di];
      int ny = cy + dy[di];
      if(min(nx,ny)>=0 && nx < n && ny < m &&
         in[nx][ny] != '#')
        Q.push(state(nx,ny,di,p,q));
    }

    if(p && in[cx][cy]=='.'){
      int nd = di^3;
      assert(0 <= nd && nd  < 4);
      int nx = cx + dx[nd];
      int ny = cy + dy[nd];
      if(min(nx,ny)>=0 && nx < n && ny < m &&
         in[nx][ny] != '#')
        Q.push(state(nx,ny,nd,p-1,q));
    }
    
    if(q && in[cx][cy]=='.'){
      int nd = di^1;
      assert(0 <= nd && nd  < 4);
      int nx = cx + dx[nd];
      int ny = cy + dy[nd];
      if(min(nx,ny)>=0 && nx < n && ny < m &&
         in[nx][ny] != '#')
        Q.push(state(nx,ny,nd,p,q-1));
    }
  }
  
  if(ans > 2*a) ans = -1;
  cout << ans << endl;
}

Measured memory_bytes: 7300
from collections import defaultdict
N = int(input())
A = [[0 for _ in range(N - 1)] for _ in range(N)]
for i in range(N):
  A[i] = [int(x) - 1 for x in input().split()]
day = 0
M = defaultdict(int)
for i in range(N):
  M[i] += 1
W = [0] * N
while M:
  day += 1
  for m in M:
    W[m] = A[m].pop(0) if A[m] else -1
  _M = defaultdict(int)
  for m in M:
    if W[m] >= 0 and W[W[m]] == m:
      _M[m] += 1
      _M[W[m]] += 1
  M = _M
for w in W:
  if w > 0:
    print(-1)
    break
else:
  print(day - 1)

Measured memory_bytes: 35948
import math

k =int(input())
ans = 0
temp_list =[]


for i in range(k):
    for j in range(k):
        temp_list.append(math.gcd(i+1,j+1))

temp_set= list(set(temp_list))

memo = [0]*len(temp_set)

for i in temp_list:
    for j in range(len(temp_set)):
        if i == temp_set[j]:
            memo[j] += 1
            break

for i in range(k):
    for j in range(len(temp_set)):
        ans += memo[j] * math.gcd(temp_set[j],i+1)

print(ans)

Measured memory_bytes: 9316
n,k = map(int,input().split())
a = list(map(int,input().split()))

ans = {}
for i in a:
    if i in ans:
        ans[i] += 1
    else:
        ans[i] = 1
#print(ans)
ans = sorted(ans.items(), key=lambda x: x[1])
#print(ans)
answer = 0
for i in range(len(ans)-k):
    answer += ans[i][1]
print(answer)

Measured memory_bytes: 38964
import string
import sys

num = set(string.digits)

a, b = map(int, input().split())
s = input()

for i in range(a+b+1):
    if i == a:
        if s[i] != '-':
            print("No")
            sys.exit()
    else:
        if s[i] not in num:
            print("No")
            sys.exit()
print("Yes")

Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
const int MOD = 1000000007;

void solve() {
  int n;
  cin >> n;
  queue<int> q;
  rep(i,n) {
    int a;
    cin >> a;
    q.push(a);
  }
  int cur = 1;
  int ans = 0;
  while(!q.empty()) {
    int temp = q.front();
    q.pop();
    if (cur != temp) ans++;
    else cur++;
  }
  if (cur != 1) cout << ans << endl;
  else cout << -1 << endl;

}

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

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

using namespace std;
using ll = long long;

int main()
{
	string s;
	cin >> s;
	if (s[0] != s[1] || s[0] != s[2] || s[1] != s[2])
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
}

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

ll dp[51][51][2505];

int main() {
    int N; cin >> N;
    int A; cin >> A;
    vector<int> x(N);
    rep(i, N){
        cin >> x[i];
    }

    for (int i = 0; i <= N; i++){
        dp[i][0][0] = 1;
    }

    for (int i = 0; i < N; i++){
        for (int j = 1; j <= i+1; j++){
            for (int k = 0; k < 2505; k++){
                if(k < x[i]){
                    dp[i+1][j][k] = dp[i][j][k];
                } else {
                    dp[i+1][j][k] = dp[i][j][k] + dp[i][j-1][k-x[i]];
                }
            }
        }
    }

    ll ans = 0;
    for (int j = 1; j <= N; j++){
        ans += dp[N][j][A*j];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 28932
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    A, B = map(int, input().split())
    ans = max(0, A - 2 * B)
    print(ans)


sol()

Measured memory_bytes: 3596
from bisect import bisect_left, bisect_right
from collections import deque
from sys import stdin


def intersect(ss, i, j, mid, v):
    i = bisect_left(ss, ss[mid+1]-v, i, mid)
    ii = bisect_left(ss, ss[j]-v, i, mid) + 1
    j = bisect_right(ss, ss[mid]+v, mid, j+1) - 1
    jj = mid+1
    acc = 0
    sjj = ss[jj+1]
    for s in ss[i:ii]:
        if sjj <= s+v:
            jj = bisect_right(ss, s+v, jj, j+1) - 1
            sjj = ss[jj+1]
        acc += jj - mid

    acc += (jj - mid) * (mid - ii)
    return acc


def count(ss, s, t, v):
    q = deque()
    ret = 0
    q.append((s, t))

    while q:
        i, j = q.popleft()
        if ss[j] - ss[i] <= v:
            ret += (j-i) * (j-i+1) // 2
        elif j - i > 1:
            mid = (i + j) // 2
            q.append((i, mid))
            q.append((mid, j))
            ret += intersect(ss, i, j, mid, v)

    return ret


def run():
    n, q = [int(x) for x in input().split()]
    s = 0
    sums = [s]
    for v in map(int, stdin.readline().split()):
        s += v
        sums.append(s)

    qs = [int(x) for x in input().split()]
    sums.append(s + max(qs))

    for v in qs:
        print(count(sums, 0, n, v))


if __name__ == '__main__':
    run()




Measured memory_bytes: 17808
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <iomanip>
#include <cmath>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N;cin>>N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    int ans = 0;
    rep(i,1,N){
        if(A[i]==A[i-1]){
            ++ans;
            A[i] = -1;
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main(){
    int n;
    cin>>n;
    ll tmp1=1,tmp2=1,tmp3=1;
    ll mod = 1e9+7;
    for(int i=0; i<n; i++){
        tmp1 *= 10;
        tmp2 *= 9;
        tmp3 *= 8;
        tmp1 %= mod;
        tmp2 %= mod;
        tmp3 %= mod;
    }
    tmp2 *= 2;
    tmp2 %= mod;
    ll ans = tmp1-tmp2;
    if(ans<0) ans+=1e9+7;
    ans += tmp3;
    ans %= mod;
    cout<<ans<<endl; 
}

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

using namespace std;

#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int main()
{
    FAST();
    vector<int>v;
    int i,k,n,x,ans=0;
    cin >> n >> k;
    for(i=0;i<n;i++)cin >> x,v.emplace_back(x);
    sort(v.begin(),v.end());
    for(i=0;i<k;i++)ans+=v[i];
    cout << ans;
    return 0;
}


Measured memory_bytes: 3600
def main():
    n, m, c = map(int, input().split())
    *b, = map(int, input().split())
    a = [[int(x) for x in input().split()] for _ in range(n)]

    ans = 0
    for i in range(n):
        if sum([a[i][j] * b[j] for j in range(m)]) > -c:
            ans += 1
    print(ans)


main()


Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

const int MAX = 100000 + 100;

struct Edge {
  int from, to, w;
};

int N;
vec<Edge, 2> G;

int dp[MAX], ans[MAX];

void dfs(int v, int p = -1) {
  dp[v] = 0;
  for (auto& e : G[v]) {
    if (e.to == p) continue;
    dfs(e.to, v);
    dp[v] = max(dp[v], dp[e.to] + e.w);
  }
}

void dfs2(int v, int p = -1, int pv = 0) {
  int deg = G[v].size();
  vector<int> top = {0};
  for (auto& e : G[v]) {
    if (e.to == p) {
      top.push_back(pv);
      continue;
    }
    top.push_back(dp[e.to] + e.w);
  }
  sort(top.rbegin(), top.rend());
  for (auto& e : G[v]) {
    if (e.to == p) continue;
    int ev;
    if (top[0] != dp[e.to] + e.w) {
      ev = top[0];
    } else {
      ev = top[1];
    }
    ev += e.w;
    dfs2(e.to, v, ev);
  }
  ans[v] = accumulate(top.begin(), top.begin() + 2, 0);
}

int main() {
  while (cin >> N) {
    G.clear();
    G.resize(N);
    for (int i = 0; i < N - 1; i++) {
      int x, y, w;
      cin >> x >> y >> w;
      G[x].push_back(Edge{x, y, w});
      G[y].push_back(Edge{y, x, w});
    }
    dfs(0);
    dfs2(0);
    int res = 0;
    for (int i = 0; i < N; i++) res = max(res, ans[i]);
    cout << res << endl;
  }
  return 0;
}



Measured memory_bytes: 26284
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
//////////////////////////////////////////////////////
const int UNIMAX = 100002;
int uni[UNIMAX] = {}; //parent -- size of member , kid -- leader name,def -1

int uniroot(int a){ //return a's leader
	if (uni[a] < 0) return a;
	return uni[a] = uniroot(uni[a]); //uni[a] => 0 , reconnect root directly
}

bool uniconnect(int a,int b){
	a = uniroot(a);
	b = uniroot(b);
	
	if(a==b) return false;
	
	if(uni[a] > uni[b]){
		a ^= b;
		b ^= a;
		a ^= b;
	}
	
	uni[a] = uni[a] + uni[b]; // membersize++
	uni[b] = a;
	return true;
}

bool uniisConnect(int a,int b){
	return (uniroot(a) == uniroot(b));
}

int unireset() {
	REP(i,UNIMAX){
		uni[i] = -1;
	}
}

int unisize (int a){
	return (-uni[uniroot(a)]);
}

int main(){
	unireset();
	int N,M; SCD2(N,M);
	int p[UNIMAX];
	
	FORq(i,1,N){
		int x; SCD(x);
		p[i] = x;
	}
	
	REP(i,M){
		int x,y;
		SCD2(x,y);
		uniconnect(x,y);
	}
	
	int ans = 0;
	FORq(i,1,N){
		if ((i==p[i]) or (uniisConnect(i,p[i]))){
			ans++;
		}
	}
	
	PRINTD(ans);
	return 0;
}

Measured memory_bytes: 1024
N, T = map(int, input().split())
lists = [list(map(int, input().split())) for i in range(N)]

cost = 1001
count = 0
for i in range(N):
    if lists[i][1] <= T:
        count += 1
        if i == 0:
            cost = lists[i][0]
        elif cost >= lists[i][0]:
            cost = lists[i][0]
        else:
            continue
    else:
        continue
if count == 0:
    print("TLE")
else:
    print(cost)


Measured memory_bytes: 3060