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

struct UnionFindTree {
    vector<int> par;
    vector<int> rank;
    vector<int> siz;

    void init(int n) {
        par.resize(n);
        rank.resize(n);
        siz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) rank[x]++;
        par[y] = x;
        siz[x] += siz[y];
    }
    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        x = find(x);
        return siz[x];
    }
};  

int main(){
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> deg(N,0);
    UnionFindTree uf;
    uf.init(N);
    for(int i=0;i<M;i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        uf.unite(a,b);
        deg[a]++;
        deg[b]++;
    }
    for(int i=0;i<K;i++){
        int c, d;
        cin >> c >> d;
        c--; d--;
        if(uf.is_same(c,d)){
            deg[c]++;
            deg[d]++;
        }
    }
    for(int i=0;i<N;i++){
        cout << uf.size(i)-deg[i]-1 << " \n"[i==N-1];
    }
    return 0;
}

Measured memory_bytes: 2432
from collections import Counter

N,K,Q = map(int,input().split())
A = [int(input())-1 for i in range(Q)]

cnt = Q-K

res = Counter(A)

for i in range(N):
    if cnt < res[i]:
        print('Yes')
    else:
        print('No')
    # print(cnt,i,res[i])

Measured memory_bytes: 11900
#include<stdio.h>
int A[2001];
int main(){
  int n,a,q,key;
  int sum=0;
  int i,j;
  A[0] = 1;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a);
    sum+=a;
    for(j=sum-a;j>=0;j--){
      if(A[j]) A[j+a]=1;
    }
  }

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(A[key]) printf("yes\n");
    else printf("no\n");
  }

  return 0;
}



Measured memory_bytes: 2108
ls1= list(map(int,input().split()))
ls = sorted(ls1)
if ls[0] == ls[1] :
    if ls[1] == ls[2]:
        print("No")
    else:
        print("Yes")
else:
    if ls[1] == ls[2]:
        print("Yes")
    else:
        print("No")
    

Measured memory_bytes: 2940
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
#define INF (1ll<<60)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;

#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)

template<class T>bool umax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool umin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;

// gcd
int gcd(int a, int b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}
// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);

    return result;
}

// sort big to small
// sort(A,A+N, greater<int>());

// v.front() = -BOUND;
// v.back() = BOUND;

// Iterator
// v.begin
// v.end

int main() {
    unsigned int N;
    cin >> N;
    vector<int> a(N,0);
    rep(i,N){
        cin >> a[i];
    }
    int A=0,B=0;

    sort(a.begin(),a.end(), greater<int>());
    rep(i,N){
        if(i%2){
            B+=a[i];
        }else{
            A+=a[i];
        }
    }
    cout << A-B << endl;
    return 0;
}



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

using namespace std;

typedef long long ll;
ll n;
ll dp[303][303];
bool use[303][303];
ll ans = 0;


int main() {
  cin >> n;


  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      cin >> dp[i][j];
   
    }
  }
  // cout << ans << endl;
  bool ok = true;
  for(int k = 0; k < n; k++) {
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
	if(dp[i][j] == dp[i][k] + dp[k][j] && dp[i][k] > 0 && dp[k][j] > 0) {
	  use[i][j] = true;
        
	}
	if(dp[i][j] > dp[i][k] + dp[k][j]) {
	  ok = false;
	  break;
	}
      }
    }
  }

  for(int i = 0; i < n; i++) {
    for(int j = 0; j <= i; j++) {
      if(!use[i][j]) ans += dp[i][j];
    }
  }

  if(ok) cout << ans << endl;
  else cout << "-1" << endl;
}
	
  
  
  


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

const double PI = acos(-1);
const double EPS = 1e-15;
using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;
const ll MOD1 = 998244353;
typedef pair<int,int> P;

#define REP(i,n) for (int i = 0; i < (n); i++)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define mp make_pair

int par[112345];
int rk[112345];

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

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

void unite (int x, int y) {
  x = fd(x);
  y = fd(y);
  if (x == y) return;

  if (rk[x] < rk[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rk[x] == rk[y]) rk[x]++;
  }
}

int main(){
  int n;
  scanf("%d", &n);
  init(112345);
  std::vector<int> a(n);
  REP(i, n) scanf("%d", &a[i]);

  for(int i = 2; i < 3333; ++i){
    int pin = -1;
    REP(j, n){
      if(a[j] % i == 0){
        if(pin == -1){
          pin = a[j];
        }else{
          unite(a[j], pin);
        }
      }
    }
  }

  std::vector<int> sorted(a);
  std::sort(sorted.begin(), sorted.end());

  int ans = 1;

  REP(i, n){
    if(fd(a[i]) != fd(sorted[i])){
      ans = 0;
    }
  }

  printf("%d\n", ans);

  return 0;
}




Measured memory_bytes: 4472
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

vector<vector<int>> g;
vector<int> dp;

int dfs(int cur){
    vector<int> child;
    for(int i=0;i<g[cur].size();i++){
        dp[g[cur][i]] = dfs(g[cur][i]);
        child.push_back(dp[g[cur][i]]);
    }
    sort(all(child),greater<int>());
    int mx = 0;
    for(int i=0;i<child.size();i++){
        mx = max(mx,child[i]+i+1);
    }
    return mx;
}

int main(){
    int n; cin >> n;
    vector<int> a(n);
    g.resize(n);
    dp.resize(n,INF);

    for(int i=1;i<n;i++){
        cin >> a[i];
        a[i]--;

        g[a[i]].push_back(i);
    }

    int ans = dfs(0);
    cout << ans << endl;
}


Measured memory_bytes: 12800
import copy

D = int(input())
C = list(map(int, input().split()))
S = []
for _ in range(D):
    s_row = list(map(int, input().split()))
    S.append(s_row)

V = []
for _ in range(D):
    v = int(input())
    V.append(v)

results = []

# 次の日に減る分も考慮して選ぶ
last = [0 for i in range(26)]
next_costs = [0 for i in range(26)]

result = 0
for d in range(D):
    for i in range(26):
        next_costs[i] = C[i] * (d+1-last[i])

    index = V[d] - 1
    next_costs_sum = sum(next_costs)
    result += S[d][index] - (next_costs_sum - C[index] * (d+1-last[index]))
    last[index] = d + 1
    results.append(result)

for result in results:
    print(result)


Measured memory_bytes: 74912
#include<bits/stdc++.h>
using namespace std;
main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N; cin >> N; int H[N]; int Max = 0;
  int ans = 0;
  for(int i = 0; i < N; i++){
    cin >> H[i];
    if(H[i] >= Max) ans++;
    Max = max(Max, H[i]);
  }
  cout << ans;
}

Measured memory_bytes: 256
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N,W = imn()
wv = [iln() for _ in range(N)]
maxv = 100 * 1000 + 1

dp = [[10**10 for _ in range(maxv)] for _ in range(N+1)]

dp[0][0] = 0

for i in range(N):
    for v in range(maxv):
        if v - wv[i][1] >= 0: dp[i+1][v] = min(dp[i+1][v], dp[i][v-wv[i][1]]+wv[i][0])
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])
ans = 0
for i in range(maxv):
    if W >= dp[N][i]: ans = max(ans, i)
print(ans)

Measured memory_bytes: 181444
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int Mod=1e9+7;
long long a[N],b[N],s;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n-1;i>=1;i--)b[i]=(b[i+1]+a[i+1])%Mod;
	for(int i=1;i<=n-1;i++)s=((s%Mod)+(a[i]*b[i]%Mod))%Mod;
	cout<<s<<endl;
}

Measured memory_bytes: 6700
<?php
// Your code here!
    $stdin = trim(fgets(STDIN));  
    $flg = false;
    $count = 0;
    for($i = 0; $i < strlen($stdin); $i++) {
        if ($flg == false && $stdin[$i] == 'R') {
            $count = 1;
            $flg = true;
        } else if ($flg && $stdin[$i] == 'R') {
            $count++;
        } else {
            $flg = false;
        }
    }
    echo $count;
?>


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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int N;
int l[110000], r[110000];
signed main() {
    cin >> N;
    for (int i = 0; i < N; i++)cin >> l[i] >> r[i];
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int> > right;
    left.push(l[0]);
    right.push(l[0]);
    int true_l = l[0], true_r = l[0], ans = 0;
    for (int i = 1; i < N; i++) {
        true_l -= r[i] - l[i];
        true_r += r[i - 1] - l[i - 1];
        if (l[i] < true_l) {
            ans += true_l - l[i];
            left.push(l[i] + left.top() - true_l); left.push(l[i] + left.top() - true_l);
            int lt = left.top();
            left.pop();
            right.push(true_l - true_r + right.top());
            true_r = true_l;
            true_l += left.top() - lt;
        } else if (l[i] > true_r) {
            ans += l[i] - true_r;
            right.push(l[i] + right.top() - true_r); right.push(l[i] + right.top() - true_r);
            int rt = right.top();
            right.pop();
            left.push(true_r - true_l + left.top());
            true_l = true_r;
            true_r += right.top() - rt;
        } else {
            left.push(l[i] + left.top() - true_l); right.push(l[i] + right.top() - true_r);
            true_l = true_r = l[i];
        }
    }
    cout << ans << endl;
}



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

using ll = long long;

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

	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	int x;
	cin>>x;

	int ans = 1000*int(x/500);
	x%=500;

	cout << ans + 5*int(x/5) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long s,t;
    cin>>s>>t;
    int con=0;
    if((s+t)%2==0)
    {
        cout<<(s+t)/2;
    }
    else
    {
        cout<<"IMPOSSIBLE"<<endl;
    }

}


Measured memory_bytes: 256
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        break
Q = collections.deque([[i, j, 0]])
sH = set()
sW = set()
while Q:
    h, w, dist = Q.popleft()
    if A[h][w] == '#':
        continue
    A[h][w] = '#'
    sH.add(h)
    sW.add(w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W:
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(sH), H - 1 - max(sH), min(sW), W - 1 - max(sW))
]))


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

int main() {
	int A, B;
	cin >> A >> B;
	int add = A + B;
	int sub = A - B;
	int mul = A * B;
	int ans = max(add, sub);
	ans = max(ans, mul);
	cout << ans << endl;
}

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

int main(){
  string S,T;
  cin >> S >> T;
  int count=0;
  for(int i=0;i<S.size();i++){
    if(S.at(i)!=T.at(i)){
      count++;
    }
  }
  cout << count << endl;
}

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

using namespace std;

using   ll=long long;
using   ld=long double;

#define fast           ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl           "\n"
#define long long      int 
#define pb             push_back
#define mp             make_pair
#define ff             first
#define ss             second
#define pll            pair<ll,ll>
#define ALL(v)         v.begin(),v.end()
#define ALLR(v)        v.rbegin(),v.rend()
#define pii            3.14159265358979323
#define inf 		   LLONG_MAX
#define ones(x)		   __builtin_popcount(x)

void solve()
{
	ll n,m,p;
	
	cin>>n>>m>>p;
	
	vector<ll> a(n);
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	vector<ll> b(m);
	
	for(int i=0;i<m;i++)
	{
		cin>>b[i];
	}
	
	ll x,y,c;
	
	vector<ll> cur;
	
	for(int i=0;i<p;i++)
	{
		cin>>x>>y>>c;
		
		cur.pb(a[x-1]+b[y-1]-c);
	}
	
	sort(ALL(cur));
	
	ll ans = cur[0];
	
	sort(ALL(a));
	sort(ALL(b));
	
	ans = min(ans,a[0]+b[0]);
	
	cout<<ans;
	
}
 
signed main()
{
 
    fast;
 
    ll t;
    
    t=1;
    
    //cin>>t;
    
    while(t--)
    {
        solve();
    }
 
    return 0;
}


Measured memory_bytes: 2936
N,M,K=map(int,input().split())
P=998244353

start=(M*pow(M-1,N-1,P))%P



if N>=2:
    fac=[0]*N
    finv=[0]*N
    inv=[0]*N
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1
    for i in range(2,N):
        fac[i]=(fac[i-1]*i)%P
        inv[i]=P-(inv[P%i]*(P//i))%P
        finv[i]=(finv[i-1]*inv[i])%P

    def comb(n,k):
        return fac[n]*(finv[k]*finv[n-k]%P)%P



    comp=0
    last=(N-1)-K #K=0ならthru
    for i in range(1,K+1):
        comp=(comp+comb(N-1,i)*pow(M-1,(N-1)-i,P))%P
    comp=(comp*M)%P

    print((start+comp)%P)

else:
    print(M%P)

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

int main()
{
  int n;
  cin >> n;
  vector<vector<int>> data(200, vector<int>(3));
  rep(i, n) cin >> data[i][0] >> data[i][1] >> data[i][2];
  int t;
  rep(i, n) if(data[i][2])
  {
    t = i;
    break;
  }
  
  for(int i = 0; i <= 100; i++)
  {
    for(int j = 0; j <= 100; j++)
    {
      bool flag = true;
      int h = data[t][2] + abs(data[t][0] - i) + abs(data[t][1] - j);
      rep(k, n)
      {
        int hh = max(h - abs(data[k][0] - i) - abs(data[k][1] - j), 0);
        if(hh != data[k][2])
        {
          flag = false;
          break;
        }
      }
      if(flag)
      {
        cout << i << " " << j << " " << h << endl;
        return 0;
      }
    }
  }
  
  cout << "illegal input" << endl;
           
  
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
def blocks(block,w,h):
    x, y, p = map(int, raw_input().split())
    if p == 1:
        for i in range(h):
            for j in range(w):
                if j < x:
                    block[i][j] = False
    if p == 2:
        for i in range(h):
            for j in range(w):
                if j >= x:
                    block[i][j] = False
    if p == 3:
        for i in range(h):
            for j in range(w):
                if i < y:
                    block[i][j] = False
    if p == 4:
        for i in range(h):
            for j in range(w):
                if i >= y:
                    block[i][j] = False
    return block

w, h, n = map(int, raw_input().split())
block = [[True for i in range(w)] for j in range(h)]
for i in range(n):
    block = blocks(block,w,h)
total = 0
for i in range(h):
    for j in range(w):
        if block[i][j] == True:
            total = total + 1
print (total)


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

#ifdef LOCAL
#define debug(var) cerr << #var << " = " << var << endl;
#else
#define debug(var)
#endif

void init() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

const int N = 54;
const long long inf = 9e18;

pair<int, int> a[N];
int xs[N], ys[N];

void solve() {
	int z, n; scanf("%d%d", &n, &z);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &a[i].first, &a[i].second);
		xs[i] = a[i].first;
		ys[i] = a[i].second;
	}
	long long ans = inf;
	sort(xs, xs+n);
	sort(ys, ys+n);
	for (int i = 0; i < n; ++i) {
		for (int j = i+1; j < n; ++j) {
			for (int k = 0; k < n; ++k) {
				for (int l = k+1; l < n; ++l) {
					int cur = 0;
					for (int m = 0; m < n && cur < z; ++m) {
						if (a[m].first >= xs[i] && a[m].first <= xs[j]
						 && a[m].second >= ys[k] && a[m].second <= ys[l]) ++cur;
					}
					if (cur >= z) {
						ans = min(ans, (long long)(xs[j]-xs[i])*(ys[l]-ys[k]));
					}
				}
			}
		}
	}
	printf("%lld", ans);
}

int main() {
	init();
	int t = 1; //scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]

from itertools import permutations
import math
l_sum = 0
dic={}
lx = list(range(0,N))

for k,i in enumerate(xy):
  l = []
  for j in xy:
    length = ((i[0]-j[0])**2 + (i[1]-j[1])**2)**(1/2)
    l.append(length)
    
  dic[k]=l
  
p = list(permutations(lx,N))
for i in p:
  for j in range(N-1):
    l_sum += dic[i[j]][i[j+1]]
    
print(l_sum/math.factorial(N))

Measured memory_bytes: 7996
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
in p2(in x){
  return 1LL<<x;
}
VI a,b;
in wy(in us, in fd, in ld){
  in sm=0;
  sm+=p2(fd+1);
  forn(i,fd+1)
    sm-=a[i]*p2(i);
  if(us==0)
    sm+=p2(ld+1);
  return min(sm,p2(fd+1));
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in ta,tb;
  cin>>ta>>tb;
  forn(i,61){
    a.PB(!!(ta&p2(i)));
    b.PB(!!(tb&p2(i)));
  }
  in c=60;
  while(c>=0 && a[c]==b[c])
    --c;
  if(c==-1){
    cout<<1<<endl;
    return 0;
  }
  in sm=0;
  sm+=wy(1,c-1,-1);
  in d=c-1;
  while(d>=0 && b[d]==0)
    --d;
  sm+=wy(0,c-1,d);
  cout<<sm<<endl;
  return 0;
}


Measured memory_bytes: 256
/* You are being watched. */


//~ while (clock() <= 69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>

//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")

using namespace std;

//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
//~ using namespace __gnu_pbds;
//~ template <typename T>
//~ using ordered_set =
  //~ tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define show(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using ll = int;
using ld = long double;
using uint = unsigned int;
using ull = unsigned int;
//using li = __int128;
//using uli = unsigned __int128;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

double getTime() {
  return clock() / (double) CLOCKS_PER_SEC;
}

void read() {};

template<typename T, typename... Args>
void read(T& a, Args&... args) {
  cin >> a;
  read(args...);
}

void print() {};

template <typename T, typename... Args>
void print(T a, Args... args) {
  cout << a << " \n"[sizeof...(args) == 0];
  print(args...);
}

const ll MOD = 2019;

void solve() {
  string s; cin >> s;
  int n = s.size();
  ll ans = 0;
  reverse(s.begin(), s.end());
  map <int, int> cnt;
  cnt[0] = 1;
  ll cur = 0;
  ll p = 1ll;
  for(int i = 0; i < n; i++) {
    cur = (cur + (s[i] - '0') * p) % 2019;
    p = (p * 10) % 2019;
    ans += cnt[cur];
    cnt[cur]++;
  }
  print(ans);
}

int main() {
  int t; t = 1;
  while(t--) solve();
}

Measured memory_bytes: 3740
import itertools
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
ans = -float('inf')
for i,j,k in itertools.product([1,-1],repeat=3):
    tmp = []
    for x,y,z in info:
        value = x*i + y*j + z*k
        tmp.append(value)
    tmp.sort(reverse=True)
    res = sum(tmp[:M])
    if res > ans:
        ans = res
print(ans)

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

#pragma warning(disable : 4996)

using namespace std;

int main()
{
	int n; scanf("%d", &n);

	vector<int> r(n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &r[i]);

		if (i % 2) { r[i] ^= 1; } // Reverse
	}

	vector<int> compress; compress.push_back(0);

	for (int i = 1; i < n; i++)
	{
		if (r[i - 1] != r[i])
		{
			compress.push_back(i);
		}
	}

	compress.push_back(n);

	int ret = 0;
	
	if (compress.size() <= 3)
	{
		ret = n;
	}
	else
	{
		for (int i = 0; i < compress.size() - 3; i++)
		{
			ret = max(ret, compress[i + 3] - compress[i]);
		}
	}

	printf("%d\n", ret);

	return 0;
}

Measured memory_bytes: 3544
#! /usr/bin/env python3
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H1, M1, H2, M2, K = map(int, read().split())
start = H1 * 60 + M1
end = H2 * 60 + M2

gap = end - start

res = gap - K

print(res)

Measured memory_bytes: 9184
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;
    static int MOD = 1000000007;

    void solve() throws IOException {

    	int n = ni();
    	int[] t = new int[n];

    	for(int i=0; i<n; i++){
    		t[i] = ni();
    	}

    	int m = ni();

    	int[] p = new int[m];
    	int[] x = new int[m];

    	for(int i=0; i<m; i++){
    		p[i] = ni();
    		x[i] = ni();
    	}

    	int z = 0;
    	for(int i=0; i<n; i++){
    		z += t[i];
    	}

    	int[] ans = new int[m];
    	for(int i=0; i<m; i++){
    		ans[i] = z - (t[p[i]-1] - x[i]);
    		out.println(ans[i]);
    	}



    }

    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }

    int ni() throws IOException {
        return Integer.parseInt(ns());
    }

    long nl() throws IOException {
        return Long.parseLong(ns());
    }

    double nd() throws IOException {
        return Double.parseDouble(ns());
    }

    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }

    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }

    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}

Measured memory_bytes: 8528
from heapq import heappush, heappop

INF = 10**15

def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    d[s] = 0
    heappush(que, (0, s))

    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                heappush(que, (d[w], w))
    return d

n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    ai, bi, ci = map(int, input().split())
    ai, bi = ai-1, bi-1
    edge[ai].append((ci, bi))
    edge[bi].append((ci, ai))

q, k = map(int, input().split())
x, y = [], []
for i in range(q):
    xi, yi = map(int, input().split())
    xi, yi = xi-1, yi-1
    x.append(xi)
    y.append(yi)

dist = dijkstra(k-1, edge)

for i in range(q):
    print(dist[x[i]]+dist[y[i]])

Measured memory_bytes: 102944
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

template<typename T>
T gcd(T a, T b) 
{
    if (b < a) { //! make sure a <= b
        T tmp = b;
        b = a;
        a = tmp;
    }

    T r = b % a;
    while (r) {
        b = a;
        a = r;
        r = b % a;
    }

    return a;
}

//! return lcm of a and b
template<typename T>
T lcm(T a, T b) 
{
    return a * b / gcd<T>(a, b);
}



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

    int N;
    LL M;
    cin >> N >> M;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    rep(i, N) a[i] /= 2;

    int p2 = 1;
    int a0 = a[0];
    while (a0 % 2 == 0) {
        a0 /= 2;
        p2 *= 2;
    }

    rep(i, N) {
        if (a[i] % p2 != 0 || (a[i]/p2) % 2 == 0) {
            cout << 0 << endl;
            return 0;
        }
    }

    LL minVal = a[0];
    for (int i = 1; i < N; ++i) {
        minVal = lcm(minVal, (LL) a[i]);
        if (M < minVal) {
            cout << 0 << endl;
            return 0;
        }
    }

    LL ans = M/minVal;
    ans -= ans / 2;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
  int A,B;
  int c = 0;
  char s[100];
  cin >> A >> B;
  cin >> s;
  for(int i = 0;strlen(s) > i;i++)
    if(s[i] == '-')
      c++;
  if(s[A] == '-')
    if(strlen(s) == (A + B + 1))
      if(c == 1)
      {
        cout << "Yes" << '\n';
        return 0;
      }
  cout << "No" << '\n';

  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

template <class T>
class EdgeBase
{
public:
    int to;
    T cost;
    EdgeBase(){};
    EdgeBase(int to0, T cost0){to = to0; cost = cost0;}
};
typedef EdgeBase<long long> Edge;

template<class T>
void shortestPath(const vector<vector<EdgeBase<T> > >& edges, int start, vector<T>& dist)
{
    const T INF = numeric_limits<T>::max();
    const T EPS = static_cast<T>(1.0e-10);

    dist.assign(edges.size(), INF);
    dist[start] = 0;
    priority_queue<pair<T,int>, vector<pair<T,int> >, greater<pair<T,int> > > q;
    q.push(make_pair(0, start));

    while(!q.empty()){
        pair<T, int> p = q.top();
        q.pop();
        int v = p.second;
        if(dist[v] < p.first - EPS)
            continue;
        for(unsigned i=0; i<edges[v].size(); ++i){
            EdgeBase<T> e = edges[v][i];
            if(dist[v] + e.cost < dist[e.to] - EPS){
                dist[e.to] = dist[v] + e.cost;
                q.push(make_pair(dist[e.to], e.to));
            }
        }
    }
}

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

    vector<vector<Edge> > edges(n);
    for(int i=1; i<n; ++i)
        edges[i].push_back(Edge(i-1, 0));
    for(int i=0; i<m; ++i){
        int l, r, c;
        cin >> l >> r >> c;
        -- l;
        -- r;
        edges[l].push_back(Edge(r, c));
    }

    vector<long long> dist;
    shortestPath(edges, 0, dist);
    if(dist[n-1] < LLONG_MAX)
        cout << dist[n-1] << endl;
    else
        cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 10104
#include <stdio.h>

void main(void){
  int N,X[100],i,T=0,min,P;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&X[i]);
  }
  for(i=0;i<N;i++){
    T=T+(X[i]-1)*(X[i]-1);
  }
  min=T;
  for(P=2;P<100;P++){
    T=0;
    for(i=0;i<N;i++){
      T=T+(X[i]-P)*(X[i]-P);
    }
    if(min>T)min=T;
  }
  printf("%d\n",min);
}


Measured memory_bytes: 1708
package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)

	X := make([]float64, n)
	var max float64
	var min float64 = 100.0
	for i := 0; i < n; i++ {
		var x float64
		fmt.Scan(&x)
		X[i] = x
		if max < x {
			max = x
		}
		if min > x {
			min = x
		}

	}

	minP := 1000000000000.0
	for j := min; j <= max; j++ {
		sum := 0.0
		for i := 0; i < n; i++ {
			v := math.Pow(X[i]-j, 2)
			sum += v
		}
		if sum < minP {
			minP = sum
		}
	}
	fmt.Println(minP)
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

int N;
double dp[110][110];
double calc(int j, int k, int V,int T) {
	if (abs(j - k) > T)return -((double)inf);
	if (j > k)swap(j, k);
	double S;
	if (k + j + T <= 2 * V) {
		S = (double)((k + T - j)*(k + 3 * j + T) + (j + T - k)*(3 * k + j + T));
		S /= 8.0;
		return S;
	}
	else {
		S = (double)(2 * V*T - (V - j)*(V - j) - (V - k)*(V - k));
		S /= 2.0;
		return S;
	}
}

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

	cin >> N;
	vector<int>T(N), V(N);
	for (int i = 0; i < N; i++)cin >> T[i];
	for (int i = 0; i < N; i++)cin >> V[i];
	for (int i = 0; i < 110;i++)for (int j = 0; j < 110; j++)dp[i][j] = -inf;
	dp[0][0] = 0.0;

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= V[i-1]; j++) {
			for (int k = 0; k <= V[i - 1]; k++) {
				dp[i][j] = max(dp[i][j],dp[i-1][k]+calc(k,j,V[i-1],T[i-1]));
			}
		}
	}
	cout << setprecision(20) << dp[N][0] << endl;
	
	return 0;
}



Measured memory_bytes: 384
#include<cstdio>
using ull = unsigned long long;

int main(){
    unsigned N;
    scanf("%u\n", &N);
    char S[N+1];
    scanf("%s", S);
    ull r = 0, g = 0, b = 0;
    for (size_t i = 0; i < N; i++){
        if(S[i] == 'R') r++;
        else if(S[i] == 'G') g++;
        else b++;
    }
    ull answer = r*g*b;
    for (size_t i = 1; i <= N - 1 >> 1; i++){
        for (size_t j = 0; j + i*2 < N; j++){
            if(S[j] != S[j + i] && S[j + i] != S[j + i*2] && S[j + i*2] != S[j]) answer--;
        }
    }
    printf("%llu\n", answer);    
	return 0;
}

Measured memory_bytes: 1704
#include<bits/stdc++.h>
using namespace std;
 
#define             ll  long long
#define            ull  unsigned long long
#define            P_B  push_back
#define            M_P  make_pair
#define         DBG(x)  printf("%s %d\n", #x, x)
#define       DBGLL(x)  printf("%s %lld\n", #x, x)
#define         SCI(x)  scanf("%d",&x)
#define         SCD(x)  scanf("%lf",&x)
#define         SCS(x)  scanf("%s",x)
#define         CLR(x)  memset(x, 0, sizeof(x))
#define        CLRN(x)  memset(x, -1, sizeof(x))
#define        SCLL(x)  scanf("%lld", &x)
#define      FOR(i, n)  for(int i = 0; i < n; i++)
#define  FORR(i, m, n)  for(int i = m; i < n; i++)
#define     SCI2(m, n)  scanf("%d%d", &m, &n)
#define  SCI3(m, n, o)  scanf("%d%d%d",&m, &n, &o)
#define     SCD2(m, n)  scanf("%lf%lf",&m,&n)
#define  SCD3(m, n, o)  scanf("%lf%lf%lf",&m,&n,&o)
#define    SCLL2(m, n)  scanf("%lld%lld", &m, &n)
#define SCLL3(m, n, o)  scanf("%lld%lld%lld",&m, &n, &o)
#define             vi  vector<int>
#define            vii  vector<pair<int, int> >
#define            vll  vector<pair<ll, ll> >
#define            Mod  1000000007
#define            INF  1000000000
 

int n, m;
queue<int> st;
vi node[100001];
vector<bool> selected(100001, false);
vector<bool> visited(100001, false);
int maxxes[100001];

void topsort(int v)
{
	if(selected[v]) return;
	selected[v] = true;
	for(auto it : node[v]){
		if(!selected[it]){
			topsort(it);
		}
	}
	st.push(v);
}

int notdfs(int v, int cnt)
{
	// cnt++;
	visited[v] = true;
	int mx =  -1;
	// DBG(mx);
	// DBG(v);
	for(auto it : node[v]){
		// if(!visited[it]){
			mx = max(mx, maxxes[it]);
			// DBG(mx);
			// DBG(it);
		// }
	}
	maxxes[v] = mx + 1;
	return mx + 1;
}

int main()
{
	SCI2(n, m);
	FORR(i, 1, m + 1){
		int p, q;
		SCI2(p, q);
		node[p].P_B(q);
	}
	FORR(i, 1, n + 1)topsort(i);
	int max_ = 0;
	FORR(i, 1, n + 1){
		int x = st.front();
		// DBG(x);
		st.pop();
		if(!visited[x]){
			max_ = max(max_, notdfs(x, -1));
		}
	}
	// FORR(i, 1, n + 1) printf("%d ", maxxes[i]);
	// cout << endl;
	printf("%d\n", max_);
}

Measured memory_bytes: 8576
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
int main(){
    int n,d,x;
    int A[100];
    cin >> n;
    cin >> d >> x;
    for (int i = 0; i < n; i++){
      cin >> A[i];
    }
    int s = 0;
    for (int i = 0; i < n; i++){
        int day = 1;
        while (day <= d){
            s++;
            day += A[i];
        }
    }
    s += x;
    cout << s << endl;;
    return 0;
}


Measured memory_bytes: 256
A, = [list(map(int, s.split())) for s in open(0)]
x, y = min(A[:2]), max(A[:2])
cds = []
for i in range(1, x + 1):
    if (x % i == 0) and (y % i == 0):
        cds.append(i)

print(sorted(cds, reverse=True)[A[2]-1])


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

int main() {
  int n;
  cin >> n;
  for(int i=1;i<=9;i++){
    for (int j=1;j<=9;j++){
      if(n==i*j){
        cout << "Yes";
        return 0;
      }
    }
  }
  cout << "No";
}


Measured memory_bytes: 3636
import java.util.Scanner;

public class Main{

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

		char [] a = sc.next().toCharArray();
		int b = 0;
		int c = 0;
		
		for(int i = 0; i <= a.length-1; i+=2) {
			if(a[i]=='L'){//奇数の条件
				System.out.println("No");
				System.exit(0);
			}
		}
		
		for(int j = 1; j <= a.length-1; j+=2) {
			if(a[j]=='R') { //偶数の条件
				System.out.println("No");
				System.exit(0);
			}
		}
		System.out.println("Yes");
	}
}
			
		










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

int main(){
  int n;
  cin >> n;
  map<string,int> cnt;
  rep(i,n){
    string s;
   cin >> s; 
    cnt[s]++;
  }
  cout << cnt.size() << endl;
}

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

using namespace std;
long long x[10000010], y[10000010];
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i < (n)i++)
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
#define pii pair<int, int>
#define int long long
#define setout(n, x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10);
const long long mod = 1e9 + 7;

signed main()
{

   cin.tie(0);
   ios::sync_with_stdio(false);

   int c;
   rep(i, 3)
   {
      cin >> x[i];
      c = x[i];
   }
   sort(x, x + 3);
   if (c == x[1])
      cout << "Yes" << '\n';
   else
      cout << "No" << '\n';
}

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

#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)
#define outl(x) cout << x << '\n';

#define INF (1 << 29)

#define FAST cin.tie(0), ios::sync_with_stdio(false)
inline int chmax(int &a, int b){return b>a ? a=b,1 : 0;}
inline int chmin(int &a, int b){return b<a ? a=b,1 : 0;}
//________

main(){
  FAST;
  int n,k;
  int a[101];
  int f;
  int sum=0;
  cin >> n >> k;
  rep(i,n){
    cin >> f;
    sum += min(2*f, abs(k-f)*2);
  }
  outl(sum);
}


Measured memory_bytes: 256
# Binary Indexed Tree (Fenwick Tree)
class BIT:
    # 1-index
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i): #[0, i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#pypyで提出すると良い。足算をするだけならbit木

#例題
## https://atcoder.jp/contests/practice2/tasks/practice2_b

N, Q = map(int, input().split())
a = list(map(int, input().split()))
B = BIT(N)
i = 0
while a:
  B.add(N-i, a.pop())
  i += 1
while Q:
  Q -= 1
  s, t, u = map(int, input().split())
  if s == 0:
    p = t + 1 #1-index
    x = u
    B.add(p, x)
  else:
    l = t + 1
    r = u + 1
    print(B.sum(r-1) - B.sum(l-1))



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

int main() {
    int n;cin>>n;
    int d[n];
    int ans = 0;
    rep(i,n)cin>>d[i];
    rep(i,n-1){
        repd(j,i+1,n){
            ans += d[i]*d[j];
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] xy = new int[n][2];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 2; j++){
                xy[i][j] = scan.nextInt();
            }
        }
        double sum = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                sum += Math.sqrt(Math.pow(xy[i][0] - xy[j][0], 2) + Math.pow(xy[i][1] - xy[j][1], 2));
            }
        }
        System.out.println(sum / n);
    }
}

Measured memory_bytes: 21844
#include <algorithm>
#include <cctype>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

int main() {
	while (1) {
		string str;
		getline(cin, str);
		if (str == "0") return 0;

		int sum = 0;
		for (int i = 0; i < str.size(); i++) {
			sum += str[i] - '0';
		}
		cout << sum << endl;
	}
	return 0;
}



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

int main() {
    int n, k;
    cin >> n >> k;
    int h[n];
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    int dp[n];
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for (int i = 2; i < n; i++) {
        int min_cost = dp[i - 1] + abs(h[i - 1] - h[i]);
        for (int j = 1; j < k && i - j - 1 >= 0; j++) {
            int x = dp[i - j - 1] + abs(h[i - j - 1] - h[i]);
            min_cost = min(min_cost, x);
        }
        dp[i] = min_cost;
    }
    cout << dp[n - 1] << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 1000000000
#define LLINF 10000000000000000ll
#define MOD 1000000007LL

bool dbgflag = false;

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

  int n;
  cin >> n;
  vector<ll> a(n), pos(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    pos[a[i]-1] = i;
  }
  set<ll> done;
  done.insert(-1); done.insert(n);
  ll sum = 0;
  for (int i = 0; i < n; i++) {
    int p = pos[i];
    int pleft = *(--done.lower_bound(p));
    int pright = *(done.lower_bound(p));
    done.insert(p);
    if (dbgflag) cout << pleft << " " << p << " " << pright << endl;
    sum += (ll)(i+1) * (p - pleft) * (pright - p);
  }

  cout << sum << endl; 
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>
#include <atcoder/all>

//#define DEBUG
#define REP(i, nn ) for(int i = 0 ; i < (int) nn; i++)
#define deb(x) std::cerr << #x << " " << x << endl;
#define debl(x) std::cerr << #x << " " << x << " ";
using namespace std;
using namespace atcoder;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
//const ll LINF = 1001002003004005006ll;
//const int INF = 1001001001;
template<typename... T>
void read(T& ... a){
    ((cin >> a),...);
}
template<typename... T>
void write(T... a){
    ((cout << a << "\n"),...);
}

template<typename... T>
void write_space(T... a){
    ((cout << a << " "),...);
}

void solve(){
    int n , m;
    read(n,m);
    dsu city(n);
    REP(i,m){
        int a, b;
        read(a,b);
        a--; b--;
        city.merge(a,b);
    }
    int numGroup = city.groups().size();
    cout << numGroup - 1 << endl;
}

int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}



Measured memory_bytes: 9040
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
const int INF = 1e9;
const int EPS = 1e-9; 

int main() {
  int N;
  cin >> N;
  vector<int> a(N), b(N);
  for (int i = 0; i < N; ++i) cin >> a.at(i) >> b.at(i);
  
  // 順列初期化
  vector<int> v(N);
  double sum = 0, ave;
  long long factN = 1;
  for (int i = 0; i < N; ++i) {
    v.at(i) = i;
    factN *= (i+1);
  }
  do {
    for (int i = 1; i < v.size(); ++i) {
      sum += sqrt((a.at(v.at(i))-a.at(v.at(i-1)))*(a.at(v.at(i))-a.at(v.at(i-1)))
                  + (b.at(v.at(i))-b.at(v.at(i-1)))*(b.at(v.at(i))-b.at(v.at(i-1)))); 
    }
  } while (next_permutation(v.begin(), v.end()));
  ave = sum / factN;
  cout << fixed << setprecision(12) << ave << endl;
}

Measured memory_bytes: 256
local s = io.read()
local n = #s
local t = {0, 0, 0}
local sstr = ""
for i = 1, n do
  sstr = s:sub(i, i)
  if(sstr == "a") then t[1] = t[1] + 1
  elseif(sstr == "b") then t[2] = t[2] + 1
  else t[3] = t[3] + 1 end
end
table.sort(t)
print(t[3] - t[1] <= 1 and "YES" or "NO")


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

int main () {
  int N;
  cin >> N;
  long long ans = 0;
  vector<int>d(N);
  for (int i = 0; i < N; i++) {
    cin >> d.at(i);
  }
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      ans += d.at(i) * d.at(j);
    }
  }
  cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 100010
#define ff first
#define ss second 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int main() {
	
	int n;
	cin>>n;
	if (n%10==9||int(n/10)==9)
		cout<<"Yes";
	else 
	cout<<"No";
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>


using namespace std;

int main() {
  string a, b, c;
  cin >> a >> b >> c;
  if(a.back() == b.front() && b.back() == c.front()) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort()
    return divisors

d1 = make_divisors(n)
d2 = make_divisors(n-1)

ans = 0
for k in d1:
    if k == 1:
        continue
    temp = n
    while temp%k == 0:
        temp //= k
    if temp%k == 1:
        ans += 1
ans += len(d2)-1
print(ans)


Measured memory_bytes: 39792
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> P;
#define min(a,b) ((a)<=(b)?(a):(b))
vector<P> card;
vector<P> solve(int x) {
	vector<P> A,B;
	int i,sum=0;
	for(i=0;i<card.size() && sum<x;i++) {
		A.push_back(card[i]);
		sum+=(card[i].second-card[i].first+1);
	}
	A[A.size()-1].second-=(sum-x);
	if((sum-x)>0) {
		B.push_back(P(card[A.size()-1].second-(sum-x)+1,card[A.size()-1].second));
	}
	for(i;i<card.size();i++) B.push_back(card[i]);
	card=B;
	return A;
}
int main() {
	int n,m,p,q,r;
	while(scanf("%d",&n),n) {
		scanf("%d",&m);
		scanf("%d %d %d",&p,&q,&r);
		card.clear();
		card.push_back(P(1,n));
		vector<P> A,B;
		for(int i=0;i<m;i++) {
			int x,y;
			scanf("%d %d",&x,&y);
			A=solve(x);
			B=solve(y-x);
			for(int j=0;j<B.size();j++) card.push_back(B[j]);
			for(int j=0;j<A.size();j++) card.push_back(A[j]);
		}
		A=solve(p-1);
		B=solve(q-p+1);
		int sum=0;
		for(int i=0;i<B.size();i++) {
			if(B[i].first<=r) {
				sum+=(min(r,B[i].second)-B[i].first+1);
			}
		}
		printf("%d\n",sum);
	}
}

Measured memory_bytes: 1376