akhauriyash/Code-Regression huggingface dataset:
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
double dot(complex<double> a, complex<double> b) {
	return a.real() * b.real() + a.imag() * b.imag();
}
double gyaku_dot(complex<double> a, complex<double> b) {
	return a.real() * b.imag() - a.imag() * b.real();
}
double leng(complex<double> a) {
	return sqrt(a.real() * a.real() + a.imag() * a.imag());
}
double angles(complex<double> a, complex<double> b) {
	double cosine = dot(a, b) / (leng(a) * leng(b));
	double sine = gyaku_dot(a, b) / (leng(a) * leng(b));
	double kaku = acos(cosine);
	if (sine <= 0) {
		kaku = 2 * Ma_PI - kaku;
	}
	return kaku;
}
vector<int> convex_hull(vector<complex<double>> a) {
	vector<int> ans;
	double now_minnest = a[0].real();
	int now_itr = 0;
	REP(i, a.size()) {
		if (now_minnest > a[i].real()) {
			now_minnest = a[i].real();
			now_itr = i;
		}
	}
	ans.push_back(now_itr);
	complex<double> ba(0, 1);
	while (true) {
		int now_go = 0;
		double now_min = 0;
		int starter = ans[ans.size() - 1];
		for (int i = 0; i < a.size(); ++i) {
			if (i != starter) {
				double goa = angles(ba, a[i] - a[starter]);
				if (goa > now_min) {
					now_min = goa;
					now_go = i;
				}
			}
		}
		if (now_go == ans[0]) break;
		ans.push_back(now_go);
		ba = complex<double>(a[now_go] - a[starter]);
	}
	return ans;
}
long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main() {
	string s;
	cin >> s;
	long long a = stoll(s);
	long long geko = 0;
	REP(i, s.length()) {
		geko += s[i] - '0';
	}
	if (a % geko) {
		cout << "No" << endl;
	}
	else cout << "Yes" << endl;
}


Measured memory_bytes: 256
def shortest_path(s,n,w,es):
    #s→iの最短距離
    # s:始点, n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    #d[i] : s→iの最短距離
    d[s] = 0
    for _ in [0]*n:
        update = False
        for p,q,r in es:
            # e: 辺iについて [from,to,cost]
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        if not update:
            break
    return d

def main():
    import sys
    input = sys.stdin.readline
    n,m,p = map(int,input().split())
    es = []
    edge = [[] for _ in range(n)]

    for _ in range(m):
        a,b,c = map(int,input().split())
        es.append([a-1,b-1,p-c])
        edge[b-1].append(a-1)
    
    ren = [False]*n
    tank = [n-1]
    while len(tank) != 0:
        new = []
        for elt in tank:
            for go in edge[elt]:
                if ren[go]:
                    continue
                ren[go] = True
                new.append(go)
        tank = new

    d = shortest_path(0,n,m,es)

    for p,q,r in es:
        # e: 辺iについて [from,to,cost]
        if d[p] != float("inf") and d[q] > d[p] + r:
            d[q] = d[p] + r
            if ren[q]:
                print(-1)
                exit()

    print(max(-d[-1],0))

if __name__ == '__main__':
    main()

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

#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";
#define tab cout<<endl;
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second

typedef long long ll;
typedef pair<ll, ll> pii;
const ll MAX = 1000005;
const ll INF = 1e9+7;
const ll LINF = 1e18 + 7;

/***************************************************************************/
int main()
{
    ll n,m;
    cin>>n>>m;
    ll ar[n],ans=0;
    for(int i=0;i<n;i++)
    {
        cin>>ar[i];
    }
    sort(ar, ar+n);
    for(int i=0;i<n;i++)
    {
        //debug2(m, ar[i]);
        if(m>=ar[i])
        {
            m-=ar[i];
            ans++;
        }
    }
    if(m>0 && ans==n)
    {
        ans--;
    }
    if(ans<0)
        ans=0;
    cout<<ans<<endl;
    return 0;
}




Measured memory_bytes: 256
def resolve():
    n = int(input())
    log26 = []
    while n > 0:
        log26.append(n%26)
        n //= 26

    ans = []
    for i in range(len(log26)-1):
        if log26[i] > 0:
            ans.append(log26[i])
        else:
            ans.append(log26[i]+26)
            log26[i+1] -= 1
    if log26[-1]!=0:
        ans.append(log26[-1])
    ans1 = []
    for i in range(len(ans)):
        ans1.append(chr(ans[i]+96))
    print("".join(ans1[::-1]))

resolve()

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

pair<int,int> parent[512][512];
int set_rank[512][512];
long long cnt[512][512][2];
string grid[512];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};


pair<int,int> find_parent(pair<int,int> x){
    if(parent[x.first][x.second] != x) parent[x.first][x.second] = find_parent(parent[x.first][x.second]);
    return parent[x.first][x.second];
}

void merge_sets(pair<int,int> x, pair<int,int> y){
    x = find_parent(x),y = find_parent(y);
    if(x == y) return;
    cnt[x.first][x.second][0] = cnt[y.first][y.second][0] = cnt[x.first][x.second][0] + cnt[y.first][y.second][0];
    cnt[x.first][x.second][1] = cnt[y.first][y.second][1] = cnt[x.first][x.second][1] + cnt[y.first][y.second][1];
    if(set_rank[x.first][x.second] > set_rank[y.first][y.second] ) parent[y.first][y.second] = x;
    else parent[x.first][x.second] = y;
    if(set_rank[x.first][x.second] == set_rank[y.first][y.second]) set_rank[y.first][y.second] += 1;
}

int main(){
    int H,W; cin>>H>>W;
    for(int i=0;i<H;i++) cin>>grid[i];
    for(int i=0;i<H;i++) for(int j=0;j<W;j++) parent[i][j] = make_pair(i,j);
    for(int i=0;i<H;i++) for(int j=0;j<W;j++) cnt[i][j][grid[i][j] == '#'?0:1] += 1;
    for(int i=0;i<H;i++) for(int j=0;j<W;j++) for(int k=0;k<4;k++){
        int ni = i + dx[k],nj = j + dy[k];
        if(ni < 0 || ni >= H || nj < 0 || nj >= W || grid[ni][nj] == grid[i][j]) continue;
        merge_sets(make_pair(i,j),make_pair(ni,nj));
    }

    long long total = 0;
    for(int i=0;i<H;i++) for(int j=0;j<W;j++) if(parent[i][j] == make_pair(i,j)) total += cnt[i][j][0] * cnt[i][j][1];
    cout<<total<<endl;
}

Measured memory_bytes: 7168
import java.io.*;

import java.util.*;

class pair{
	int a ;int b;
	public pair(int a,int b){
		this.a=a;
		this.b=b;
	}}

public class Main {
	
	public static void solve(String s1,String s2) {
		
	}

	public static void main(String[] args) throws IOException 
	{ 

		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		int m=s.nextInt();
		int[] arr=new int[n];
		TreeMap<Integer,TreeSet<Integer>> maxi=new TreeMap<>();
		for (int i = 0; i < arr.length; i++) {
			arr[i]=s.nextInt();
			maxi.put(i+1,new TreeSet<>());
		}
		int[][] edge=new int[m][2];
		HashSet<Integer> jj=new HashSet<>();
		
		for (int i = 0; i < edge.length; i++) {
			edge[i][0]=s.nextInt();
			edge[i][1]=s.nextInt();
			jj.add(edge[i][0]);
			jj.add(edge[i][1]);
			maxi.get(edge[i][0]).add(arr[edge[i][1]-1]);
			maxi.get(edge[i][1]).add(arr[edge[i][0]-1]);
			
			
		}
		int ans=0;
		for (int i = 0; i < n; i++) {
			int temp=arr[i];
			if(!jj.contains(i+1)) {
				ans++;
				continue;
			}
			if(maxi.get(i+1).last()<temp)
				ans++;
			
		} 
		System.out.println(ans);
		


	}


}

Measured memory_bytes: 98208
#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int n) {
  if (n == 2)
    return true;
  else if (n < 2 || n%2 == 0)
    return false;
  int i = 3;
  while (i <= sqrt(n)) {
    if (n%i == 0)
      return false;
    i += 2;
  }
  return true;
}

int main() {
  int N, cnt = 0;
  int a[10000];

  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    if (isPrime(a[i]))
      cnt++;
  }
  cout << cnt <<endl;

  return 0;
  
}

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

int main()
{
    int n;
    std::cin >> n;
    std::vector<int> vi(n);
    for (auto i = 0; i < n; ++i)
    {
        std::cin >> vi[i];
    }
    std::sort(vi.begin(), vi.end());
    std::cout << std::distance(vi.begin(), std::unique(vi.begin(), vi.end())) << std::endl;
    return 0;
}


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

int main() {
  
  int n;
  cin>>n;
  
  int hum=0;
  
  for(int i=0;i<n;i++){
    int l,r;
    cin>>l>>r;
    
  hum+=r-l+1;
  }
  cout<<hum<<endl;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 5e5 + 5;
multiset<int,greater<int>> s[maxn];
int n , a[maxn];

int main(){
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    int n;cin >> n;
    ll resl = 0 , resr = 0;
    bool dif = 0;
    int res = 1e9;
    for(int i = 1 ; i <= n ; ++i){
        int x , y;cin >> x >> y;
        if(x > y)res = min(res , y);
        resl += x;
        dif |= (x != y);
    }
    if(dif)cout << resl - res;
    else cout << 0;
}



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

int main()
{
    int n;
    cin >> n;
    if (n%10 == 3) {
        cout << "bon" << endl;
    } else if (n%10 == 2) {
        cout << "hon" << endl;
    } else if (n%10 == 4) {
        cout << "hon" << endl;
    } else if (n%10 == 5) {
        cout << "hon" << endl;
    } else if (n%10 == 7) {
        cout << "hon" << endl;
    } else if (n%10 == 9) {
        cout << "hon" << endl;
    } else {
        cout << "pon" << endl;
    }
    return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int> cost(N);
  for(int i=0;i<N;i++){
    cin>>cost.at(i);
  }
  sort(cost.begin(),cost.end());
  int sum = 0;
  for(int i=0;i<N-1;i++){
    sum+=cost.at(i);
  }
  cout<<sum+cost.at(N-1)/2<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;

const int MAX_N = 1 << 17;

// セグメント木を持つグローバル配列
int n, dat[2*MAX_N-1];

// 初期化
void init (int n_) {
    // 簡単のため、要素数を2の冪乗に
    n = 1;
    while(n < n_) n *= 2;

    // 全ての値をINT_MAXに
    for (int i = 0; i < 2*n - 1; i++) dat[i] = INT_MAX;
}

// k番目の値(0-indexed)をaに変更
void update(int k, int a) {
    // 葉の節点
    k += n - 1;
    dat[k] = a;
    //　登りながら更新
    while(k > 0) {
        k = (k - 1) / 2;
        dat[k] = min(dat[k*2+1], dat[k*2+2]);
    }
}

// [a, b)の最小値を求める
// 後ろの方の引数は、計算の簡単のための引数。
// kは節点の番号、l、rはその節点が[l, r)に対応付いていることを表す。
// したがって、外からはquery(a, b, 0, 0, n)として呼ぶ。

int query(int a, int b, int k, int l, int r) {
    // [a, b)と[l, r)が交差しなければINT_MAX
    if (r <= a || b <= l) return INT_MAX;

    // [a, b)が[l, r）を完全に含んでいれば、この節点の値
    if (a <= l && r <= b) return dat[k];
    else {
        // そうでなければ、二つの子の最小値
        int vl = query(a, b, k*2+1, l, (l+r) / 2);
        int vr = query(a, b, k*2+2, (l+r)/2, r);
        return min(vl, vr);
    }
}

int main(){
    int n_, q;
    cin >> n_ >> q;
    init(n_);
    int t, a, b;
    rep(i, q) {
        cin >> t >> a >> b;
        if (t == 0) {
            update(a, b);
        } else {
            cout << query(a, b+1, 0, 0, n) << endl;
        }
    }
}


Measured memory_bytes: 4108
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main(void){
    int A, B;
    cin >>A >> B;

    if((A+B) % 2 == 0){
        cout << (A+B)/2 << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 10000;

int par[MAX_N];
int rank[MAX_N];

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

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

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

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

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

main(){
  int n, q;
  cin >> n >> q;
  init(n);
  for(int i=0;i<q;i++){
    int a, b, c;
    cin >> a >> b >> c;
    if(a) cout << same(b, c) << endl;
    else unite(b, c);
  }
}

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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;

typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define Y first
#define X second
#define ALL(x) (x).begin(), (x).end()
#define RANGE(x, y, maxX, maxH) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxH))
#define MP(x, y) make_pair(x, y)

const int INF = 0x3f3f3f3f;
const int DX[] = {1, 0, -1, 0};
const int DY[] = {0, 1, 0, -1};

int W, H;
VVI ts;
VI cs;

struct State {
    State(){}
    State (PII p_, int dir_, int cost_) : p(p_), dir(dir_), cost(cost_) {}

    PII p;
    int dir; // ??????
    int cost;

    bool operator > (const State &s) const {
        return cost > s.cost;
    }

    void dump() {
        cout << p.X << " " << p.Y << " " << dir << " " << cost << endl;
    }

    void dump(string pre) {
        cout << pre << p.X << " " << p.Y << " " << dir << " " << cost << endl;
    }
};

void dump_dist(VVVI &dist) {
    for (int k = 0; k < 4; k++) {
        for (int y = 0; y < H; y++) {
            for (int x = 0; x < W; x++) {
                int c = dist[y][x][k];
                cout << (c == INF ? -1 : c) << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
}

int solve() {
    VVVI dist(H, VVI(W, VI(4, INF))); // ????°??????????
    dist[0][0][0] = 0;
    priority_queue<State, vector<State>, greater<State>> q;
    q.push(State(MP(0, 0), 0, 0));
    
    while (q.size()) {
        State cur = q.top();
        q.pop();

//        cur.dump("-- ");

        // ???????????????????????????
        if (cur.cost > dist[cur.p.Y][cur.p.X][cur.dir]) continue;

        // 4???????????????
        for (int i = 0; i < 4; i++) {
            State n;

            n.cost = cur.cost + (ts[cur.p.Y][cur.p.X] == i ? 0 : cs[i]);

            n.dir = (cur.dir + i) % 4;

            n.p.Y = cur.p.Y + DY[n.dir];
            n.p.X = cur.p.X + DX[n.dir];

            // ??´???
            if (!RANGE(n.p.X, n.p.Y, W, H)) continue;

//            n.dump("** ");

            if (dist[n.p.Y][n.p.X][n.dir] > n.cost) {
                dist[n.p.Y][n.p.X][n.dir] = n.cost;
                q.push(n);
            }
        }
    }

//    dump_dist(dist);

    int ans = *min_element(ALL(dist[H - 1][W - 1]));

    return ans == INF ? -1 : ans;
}

int main(void) {
    while (cin >> W >> H, W) {
        ts.clear();
        ts.resize(H, VI(W));
        cs.clear();
        cs.resize(4);

        for (int y = 0; y < H; y++) {
            for (int x = 0; x < W; x++) {
                cin >> ts[y][x];
            }
        }

        for (int i = 0; i < 4; i++) {
            cin >> cs[i];
        }

        cout << solve() << endl;
    }

}

Measured memory_bytes: 1376
# include<bits/stdc++.h>
# include<unordered_map>
# include<unordered_set>
//# include<prettyprint.hpp>
using namespace std;
# define ll long long
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n; cin >> n;
    vector<ll> a(n);
    map<ll, ll> m;
    for(ll i = 0; i < n; i++){
        cin >> a[i];
        m[i-a[i]]++;
    }
    ll ans = 0;
    for(ll i = 0; i < n; i++){
        m[i-a[i]]--;
        ans+=m[a[i]+i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 27320
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i < int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

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

	int ret = 0;

	FOR(k,0,K+1){
		FOR(i,0,K+1){
			if(0 <= S - k -i && S - k -i <= K) ret++;
		}
	}

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


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

typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))
#define min3(x, y, z) min(x, min(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif

using namespace std;
int main(){
    int N;
    string s;
    cin >> N >> s;
    int q = 0;
    int e = 0;
    rep(i,N){
        if (s[i] == 'W'){
            q++;
        }
    }
    //cout << q;
    rep(i,N-q){
        if(s[i] == 'W'){
            e++;
        }
    }
    cout << e;
    return 0;
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
rep(i,N) {
  cin >> list[i];
}
//配列(スタックとしても使える)
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
//ソート クイックだからO(NlogN)
sort(all(list));
sort(all(list), greater<int>());

//配列の内容表示
dout << "====listの内容====\n";
for (int edp = 0; edp < N; edp++) dout << list[edp] << endl;
dout << "====ここまで====\n";


//配列の最小最大(Nは要素数)
*min_element(all(c))
*max_element(all(c))

//a[0]からa[N]を逆順にする(計算量はO(N))
reverse(all(a));
//listの末尾に要素を追加
list.push_back(10);
//listの末尾から要素を削除
list.pop_back();
//空ですか？
list.empty()



//キュー(待ち行列)
//定義
queue<int> a;
//追加
a.push(x);
//取る
a.pop();
//チェック
a.front()
//サイズ
a.size()
//空ですか
a.empty()



//優先度付きキュー※全部計算量がO(NlogN)あるので注意
// int 型の要素を持ち、最も小さい値を取り出す形の priority_queue を定義
priority_queue<int, vector<int>, greater<int>> Q1;
// double 型の要素を持ち、最も大きい値を取り出す形の priority_queueを定義
priority_queue<double, vector<double>, less<double>> Q2;
//追加
a.push(x);
//取る
a.pop();
//一番小さいの教えて下さい
a.top()
//サイズ
a.size()
//空ですか
a.empty()



//部分文字列
//添字3から5文字
s.substr(3,5)
//添字3から全部
s.substr(3)

//入れ替え
swap(a,b);



// int 型の番地に string 型の変数を記録する場合（2^31 要素の string型配列と同じような感じ）
map<int, string> mp;
for (auto itr =mp.begin(); itr != mp.end(); itr++) {
    //順番にマップを眺める。itr->firstでキー、itr->secondがバリュー
}

//ソート済みのaの中で初めてx以上になるインデックスを返す
lower_bound(all(a), x) - a

//next_permutation
do {
  //ここにパーテーションがくる
} while (next_permutation(s.begin(), s.end()));

//set
set<int> hoge;
hoge.insert(50);  //hogeに挿入。重複は無視される。
hoge.insert(20);  //内部は小さい順に並ぶ
hoge.erase(50);   //hogeから消し去る。
//40以上である最小の要素を指すイテレーターを返す。
//もちろんそんなものはないからEndが出力される
auto itr1 = Set.lower_bound(40);
if (itr1 == Set.end()) cout << "End" << endl;
else cout << (*itr1) << endl;

//pair
//たくさんつくる
vector<pair<int,string>> hoge(10);
//参照
hoge[0].first
sort(all(hoge), greater<pair<int, string>>());




*/


Measured memory_bytes: 3752
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<pair<ll, ll>> pll;
 
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
 
const long double PI = acos(-1);
 
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}


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

  ll n;
  cin >> n;
  vector<ll> t(n);
  for(ll i = 0; i < n; i++) cin >> t[i];
  ll m;
  cin >> m;
  vector<ll> ans(m);
  for(ll i = 0; i < m; i++){
    ll p, x;
    cin >> p >> x;
    for(ll j = 0; j < n; j++){
      if(j+1 == p) ans[i] += x;
      else ans[i] += t[j];
    }
  }

  for(auto i : ans) cout << i << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
typedef long long int ll;
typedef long double ld;
#define PI 3.141592653589793
#define MOD 1000000007
#define ALL(obj) (obj).begin(),(obj).end()
template<class T>inline bool chmax(T& a,T b){if (a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T& a,T b){if (a>b){a=b;return 1;}return 0;}
const ll INF = 1LL << 60;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
//四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct edge{//グラフに使うヤツ
    ll from,to,cost;
};

typedef vector<vector<edge> > G;
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

int main(){
    ll h,w;
    cin >> h >> w;
    string s[h];
    for (ll i=0;i<h;i++){
        cin >> s[i];
    }
    ll ans=0;
    for (ll i=0;i<h;i++){
        for (ll j=0;j<w;j++){
            if (s[i][j]=='#'){
                continue;
            }
            ll cost[h][w];
            memset(cost,-1,sizeof(cost));
            cost[i][j]=0;
            queue<pair<ll,ll> > que;
            que.push(make_pair(i,j));
            while(!que.empty()){
                pair<ll,ll> p=que.front();
                que.pop();
                ll x=p.first,y=p.second;
                for (ll i=0;i<4;i++){
                    ll x2=x+dx[i],y2=y+dy[i];
                    if (x2>=0 and x2<h and y2>=0 and y2<w and s[x2][y2]=='.' and cost[x2][y2]==-1){
                        cost[x2][y2]=cost[x][y]+1;
                        que.push(make_pair(x2,y2));
                        ans=max(cost[x2][y2],ans);
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18+20;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int H,W,N;
	cin >> H >> W >> N;
	vector<int> A(N);
	for(int i=0;i<N;++i){
		cin >> A[i];
	}
	vector< vector<int> > fld(H,vector<int>(W,-1) );
	int index = 0;
	int R = 0;
	int C = 0;
	for(int r=0;r<H;++r){
		R = r;
		for(int c=0;c<W;++c){
			if( R &1 ){
				C = W-c-1;
			}else{
				C = c;
			}
			fld[R][C] = index;
			A[index]--;
			if( A[index] == 0 ){
				++index;
			}
		}
	}
	for(int r=0;r<H;++r){
		for(int c=0;c<W;++c){
			if( c ) cout << " ";
			cout << fld[r][c]+1;
		}
		cout << endl;
	}
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define yn(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YN(ans) if(ans)printf("YES\n");else printf("NO\n")
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}

int main(){
    int h,w;
    in(h,w);
    int array[h+1][w+1];
    int sum=0;
    rep(i,h){
        sum=0;
        rep(j,w){
            cin>>array[i][j];
            sum+=array[i][j];
        }
        array[i][w]=sum;
    }
    rep(i,w+1){
        sum=0;
        rep(j,h){
            sum+=array[j][i];
        }
        array[h][i]=sum;
    }
    rep(i,h+1){
        rep(j,w+1){
            if(j!=0)cout<<" ";
            cout<<array[i][j];
        }
        cout<<endl;
    }
}



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


using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0; i<ll(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 1000000007;



int main() {

	int n, k;
	cin >> n >> k;

	vector<ll> h(n);
	REP(i, n)cin >> h[i];

	sort(ALL(h));
	reverse(ALL(h));

	ll ans = 0;

	FOR(i, k, n) {
		ans += h[i];
	}
	cout << ans << endl;

}

Measured memory_bytes: 1792
#include <stdio.h>
#include <math.h>
 
int isPrime(int);
 
int main(){
 
  int n,data[100000],i,c=0;
 
  scanf("%d",&n);
 
  for(i=0 ; i<n ; i++){
    scanf("%d",&data[i]);
    if(isPrime(data[i])==0) c++;
  }
 
printf("%d\n",c);
 
return 0;
 
}
 
 
int isPrime(int x){
 
  int i,sq;
 
  sq=(int)sqrt(x);
 
  if(x==2) return 0;
  else if(x<2) return 1;
  else if(x%2==0) return 1;
 
  else{
    i=3;
    while(i<=sq){
      if(x%i==0) return 1;
      i+=2;
    }
  }
 
  return 0;
}


Measured memory_bytes: 2140
#!/usr/bin/env python3
import copy
H, W, K = map(int, input().split())

w_list = [None,1]

for i in range(W-1):
	w_list.append(0)

fibo = [1, 1, 2, 3, 5, 8, 13, 21]

if W>=2:
	for step in range(1,H+1):
		w_list_temp = copy.copy(w_list)
		# 1 or W
		w_list[1] = w_list_temp[1] * fibo[W-1] + w_list_temp[2] * fibo[W-2]
		w_list[W] = w_list_temp[W] * fibo[W-1] + w_list_temp[W-1] * fibo[W-2]
		for Ind in range(2,W):
			w_list[Ind] =  w_list_temp[Ind]   * fibo[Ind-1] * fibo[W-(Ind-1)-1] \
						 + w_list_temp[Ind-1] * fibo[Ind-2] * fibo[W-(Ind-1)-1] \
						 + w_list_temp[Ind+1] * fibo[Ind-1] * fibo[W-(Ind-1)-2]

print(w_list[K]%1000000007)


Measured memory_bytes: 3444
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> P;


const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
 
int fact[N], ifact[N];
 
int inv(int a, int m) {
    if (a == 0) return 0;
    int k = -inv(m%a,a);
    if (k < 0) k += a;
    return (ll(m)*k+1)/a;
}
 
int comb(int m, int n) {
    if (n < 0 || n > m) return 0;
    return (ll) fact[m] * ifact[n] % MOD * ifact[m-n] % MOD;
}

void init(){
    fact[0] = 1;
    for (int n = 1; n < N; n++) fact[n] = ll(n) * fact[n-1] % MOD;
    ifact[N-1] = inv(fact[N-1], MOD);
    for (int n = N-2; n >= 0; n--) ifact[n] = ll(n+1) * ifact[n+1] % MOD;
}

int main() {
  int n, k;
  cin >> n >> k;
  vi a(n);
  rep (i, n) cin >> a[i];
  init();

  sort(a.begin(), a.end());
  ll s_min=0, s_max=0;
  rep(i, n - k + 1){
    ll c = comb(n - i - 1, k - 1);
    s_min += a[i] * c % MOD;
    s_max += a[n-i-1] * c % MOD;
  }
  ll ans = (s_max - s_min) % MOD;

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

Measured memory_bytes: 1408
#include <cstdio>

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int main()
{
  int n;
  int a[100001];
  int b[100000];
  scanf("%d", &n);
  for (int i = 0; i <= n; ++i)
  {
    scanf("%d", a + i);
  }
  for (int i = 0; i < n; ++i)
  {
    scanf("%d", b + i);
  }
  long long ans = 0;
  for (int i = 0; i < n; ++i)
  {
    ans += min(a[i], b[i]);
    b[i] -= min(a[i], b[i]);
    if (b[i] > 0)
    {
      ans += min(b[i], a[i + 1]);
      a[i + 1] -= min(b[i], a[i + 1]);
    }
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n;
map<string,int> a;
vi b,c;
vector<vs> d;

vvi g;

int main(){
	while(1){
		cin>>n;
		if(!n) break;
		b=c=vi(n);
		d=vector<vs>(n);
		g=vvi(n);
		for(int i=0;i<n;i++){
			string s;
			cin>>s>>b[i]>>c[i];
			a[s]=i;
			d[i]=vs(c[i]);
			for(int j=0;j<c[i];j++) cin>>d[i][j];
		}
		for(int i=0;i<n;i++) for(int j=0;j<c[i];j++) g[i].push_back(a[d[i][j]]);
		int N=n/2,res=0;
		vi dp(1<<N);
		vl S(n);
		for(int i=1;i<1<<N;i++){
			int v,I=i;
			for(int j=0;j<N;j++) if(i&1<<j){
				v=j+n-N;
				break;
			}
			I-=1<<v-n+N;
			for(int j=0;j<g[v].size();j++){
				int u=g[v][j];
				if(u>=n-N&&I&1<<u-n+N) I-=1<<u-n+N;
			}
			dp[i]=max(dp[i&i-1],dp[I]+b[v]);
		}
		for(int i=0;i<n;i++) for(int j=0;j<g[i].size();j++) S[i]+=1ll<<g[i][j];
		for(int i=0;i<1<<n-N;i++){
			int I=(1<<N)-1,sum=0;
			bool f=1;
			for(int j=0;j<n-N;j++) if(i&1<<j){
				sum+=b[j];
				if(S[j]&i) f=0;
				I&=(1<<N)-1-(S[j]>>n-N);
			}
			if(f&&i&1) res=max(res,dp[I]+sum);
		}
		cout<<res<<endl;
	}
}

Measured memory_bytes: 7660
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;


int main(int argc, const char * argv[]) {
  int n, k;
  cin >> n >> k;
  vector<int> l(n);
  for(int i = 0; i < n; i++){
    cin >> l.at(i);
  }
  
  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());
  int result = 0;
  for(int i = 0; i < k; i++){
    result += l.at(i);
  }
  cout << result << endl;
  return 0;
}


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

const int N = 1e5 + 10;
using namespace std;

struct person {
	int a, b, c;
	void read() {
		cin >> a >> b >> c;
	}
};

long long n, X, Y, Z, a[N], b[N], c[N];
set <pair <long long, int> > leftHand[3], rightHand[3];
person p[N];

int main() {
	cin >> X >> Y >> Z;
	n = X + Y + Z;
	for (int i = 0; i < n; i++) 
		p[i].read();

	sort (p, p + n, [] (person i, person j) {
		return i.b - i.c > j.b - j.c;
	});
	for (int i = 0; i < n; i++)
		a[i] = p[i].a, b[i] = p[i].b, c[i] = p[i].c;

	long long curVal = 0;

	for (int i = 0; i < Y; i++) {
		leftHand[0].insert({b[i] - a[i], i});
		curVal += b[i];
	}

	for (int i = Y; i < n; i++) {
		rightHand[0].insert({c[i] - a[i], i});
		curVal += c[i];
	}
	for (int i = 0; i < X; i++) {
		auto h = *rightHand[0].begin();
		rightHand[0].erase(h);
		rightHand[1].insert(h);
		curVal += a[h.second] - c[h.second];
	}

	long long ans = curVal;

	for (int e = Y; e < Y + X; e++) {
		int flag = -1;
		for (auto i: {0, 1})
			if (rightHand[i].find({c[e] - a[e], e}) != rightHand[i].end()) {
				rightHand[i].erase({c[e] - a[e], e});
				curVal -= (i == 0)? c[e] : a[e];
				flag = i;
				if (i == 0) {
					auto h = *rightHand[1].rbegin();
					rightHand[1].erase(h);
					rightHand[0].insert(h);
					curVal += c[h.second] - a[h.second];
				}
			}
		assert(flag > -1);

		leftHand[1].insert({b[e] - a[e], e});
		curVal += a[e];

		assert (leftHand[0].size() == Y && rightHand[0].size() == Z
			&& leftHand[1].size() + rightHand[1].size() == X);

		if (*leftHand[1].rbegin() > *leftHand[0].begin()) {
			auto v = *leftHand[1].rbegin();
			auto u = *leftHand[0].begin();
			curVal += a[u.second] - a[v.second];
			curVal += b[v.second] - b[u.second];
			leftHand[0].erase(u);
			leftHand[1].erase(v);
			leftHand[1].insert(u);
			leftHand[0].insert(v);
		}

		ans = max(ans, curVal);
	}
	cout << ans << endl;
}

// SamMHD :: May24-2019 :: Another Soale Jazzzzab...

Measured memory_bytes: 12032
n, m = map(int, input().split())
nop = [0]*m

for i in range(n):
    l = list(map(int, input().split()))
    # print(l)
    for j in range(l[0]):
        nop[l[j+1]-1] += 1

# print(nop, n)

print(nop.count(n))


Measured memory_bytes: 2940
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;
// typedef vector<int> v;

#define rep(i, c) for(int i = 0; i < int(c); i++)
#define ALL(x) (x).begin(), (x).end() //sort(ALL(obj))みたいな
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値
#define pb push_back //




int main() {
  int n;
  cin >> n;
  cout << 2*n*3.1415926535 << endl;
}


Measured memory_bytes: 3260
import java.util.Scanner;

public class Main{

	static int mod = 1000000007;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		
		long []a = new long [n];
		
		long b = 0;
		
		for(int i = 0 ;i < n ;i++) {
			a[i] = Long.parseLong(sc.next());
		}
		long ans = 0;
		long p = 1;
		
		for(int i = 0 ;i < 60 ;i++) {
			long cnt = 0;
			for(int j = 0 ;j < n ;j++) {
				cnt += a[j] >>> i & 1;
			}
			long temp = (n - cnt) * cnt % mod;
			ans = (ans + temp * p % mod)%mod;
			
			p = p * 2 % mod;
		}
		
		System.out.println(ans);

	}

}


Measured memory_bytes: 65856
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL
#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

#ifdef LOCAL
struct PrettyOS {
    ostream& os;
    bool first;
    template <class T> auto operator<<(T&& x) {
        if (!first) os << ", ";
        first = false;
        os << x;
        return *this;
    }
};
template <class... T> void dbg0(T&&... t) {
    (PrettyOS{cerr, true} << ... << t);
}
#define dbg(...)                                            \
    do {                                                    \
        cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \
        dbg0(__VA_ARGS__);                                  \
        cerr << endl;                                       \
    } while (false);
#else
#define dbg(...)
#endif

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "P(" << p.first << ", " << p.second << ")";
}

template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[";
    for (auto d : v) os << d << ", ";
    return os << "]";
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int m, d;
    cin >> m >> d;

    int ans = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 10; j <= d; j++) {
            int j0 = j / 10, j1 = j % 10;
            if (j0 <= 1 || j1 <= 1) continue;
            if (i == j0 * j1) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
a, b, c, x, y = [ int(v) for v in input().split() ]
ans = 10**10
for i in range(max(x,y)*2+2):
    x_i, y_i = x - i // 2, y - i // 2
    if x_i < 0:
        x_i = 0
    if y_i < 0:
        y_i = 0
    total = x_i * a + y_i * b + c * i
    ans = min(ans,total)

print(ans)



Measured memory_bytes: 40940
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) ll aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) string aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main() {
	
	int N;
	cin>>N;
	int dp[N][N];
	int field[N][N];
	fx(N){
		fy(N){
			cin>>dp[x][y];
			field[x][y]=dp[x][y];
		}
	}
	
	
	fy(N){
		fx(N){
			fz(N){
				dp[x][z]=min(dp[x][z],dp[x][y]+dp[y][z]);
			}
		}
	}
	bool flag=true;
	fx(N){
		fy(N){
			if(field[x][y]!=dp[x][y]){
				flag=false;
				x=N;y=N;
			}
		}
	}
	
	if(flag){
		ll ans=0;
		fx(N){
			fz(N){
				bool plus=true;
              if(x==z){continue;}
				fy(N){
                   if(x==y||z==y){continue;}
				if(dp[x][z]==dp[x][y]+dp[y][z]){
					plus=false;
					break;
				}
			}
			if(plus){
				ans+=dp[x][z];
			}
		}
	}
	ce(ans/2)
	}else{
		ce(-1)
	}
  
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
int arr[501][501];

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	for(int j=2; j<=n; j++) {
		arr[j-1][j] = 1;
		for(int i=j-2; i>=1; i--) {
			int t = 1;
			for(int f=2;;f*=2) {
				if((j-i)%f != 0) break;
				t++;
			}
			arr[i][j] = t;
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=i+1; j<=n; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << '\n';
	}
}

Measured memory_bytes: 1536
#!/usr/bin/perl

use utf8;
use strict;


my $n = <STDIN>;
chomp $n;

my %restaurant_num = {};
my %restaurant = {};
for(my $i = 0; $i < $n; $i++) {
    my $line = <STDIN>;
    chomp $line;
    my ($city, $point) = split(/ /, $line);
    $restaurant{$city} .= "$point,";
    $restaurant_num{$city."_".$point} = $i + 1;
}

foreach my $city (sort {$a cmp $b} keys %restaurant) {
    $restaurant{$city} =~ s/,$//;
    foreach my $point (sort {$b <=> $a} split(/,/, $restaurant{$city})) {
        print $restaurant_num{$city."_".$point}."\n";
    }
}

exit;

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define vec vector<ll>
#define mat vector<vector<ll> >
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef complex<double> comp;
const ll INF=1e9+7;
const ll inf=INF*INF;
const ll MOD=998244353;
const ll mod=MOD;
const int MAX=200010;

signed main(){
    ll n;cin>>n;
    ll x,m;cin>>x>>m;
    ll ans=0;
    vector<ll>used(m,-1);
    vector<ll>sum(m+1);
    vector<ll>c(0);
    ll now=0;
    while(used[x]<0){
        used[x]=now;
        if(now)sum[now]=sum[now-1]+x;
        else sum[now]=x;
        x=x*x%m;
        now++;
    }
    sum[now]+=sum[now-1]+x;
    if(n<=now){
        cout<<sum[n-1]<<endl;
    }else{
        ans+=sum[used[x]];
        ll s=now-used[x];
        ll v=sum[now]-sum[used[x]];
        n-=used[x]+1;
        ans+=(n/s)*v;
        ans+=sum[used[x]+n%s]-sum[used[x]];
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 4752
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <numeric>




typedef long long ll;
#define PI 3.14159265359
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define mp make_pair
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBAC
#include <functional>
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

ll gcd(ll a, ll b) {
	ll c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

ll lcm(ll a, ll b) {
	ll c;
	c = a * b / gcd(a, b);
	return c;
}

int sort_greater(int m, int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
	return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t, sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

bool is_prime(int x) {
	if (x <= 1) return false;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

const ll mod = 1000000007;

map<string, int> memo;

using P=pair<ll,ll>;

/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
ll findIndex(int value, vector<ll> a)
{

	for (ll i = 0; i < (ll)a.size(); i++) {
		if (a[i] == value) {
			return i;
		}
	}
	return -1;
}

ll nCr(ll n, ll r) {
	ll a = 1;
	for (ll i = n; i > n - r; --i) {
		a = a * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		a = a / i;
	}
	return a;
}



const int INF = 1001001001;



int main() {
	int n,k;
	cin >> n>>k;
	vector<int> p(n);
	rep(i, n)cin >> p[i];
	sort(all(p));
	ll ans = 0;
	rep(i, k) {
		ans += p[i];
	}
	cout << ans << endl;
	return 0;
}













Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const ll MOD2=998244353;
const double PI=acos(-1);
const ll INF=1e18;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll H,M,h,m,k;
  cin >> H >> M >> h >> m >> k;
  cout << (h-H)*60+(m-M)-k << endl;
}

Measured memory_bytes: 3640
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;
const int MOD = 1e9 + 7;
typedef long long ll;
map<ll, ll> m;
ll f(ll n) {
	return m[n] > 0 ? m[n]: (m[n] = (f(n / 2) + f((n - 1) / 2) % MOD + f((n - 2) / 2)) %MOD);
}
int main() {
	ll n;
	scanf("%lld", &n);
	m[0] = 1;
	m[1] = 2;
	printf("%lld\n", f(n));
	return 0;
}

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

int main() {
  long long N, A, B;
  cin >> N >> A >> B;
  
  long long remain = N%(A+B);
  long long b = 0;

  if(remain <= A) b = A*(N/(A+B)) + remain;
  
  else b = A*(N/(A+B)) + A;
  
  cout << b << endl;
}

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

int n,q;
int counter[200000];
vector<int> children[200000];
bool visited[200000];

void dfs(int v) {
  visited[v] = true;
  for(auto u : children[v]) {
    if(visited[u]) continue;
    counter[u] += counter[v];
    dfs(u);
  }
}

signed main() {
  cin >> n >> q;
  rep(i, n-1) {
    int a,b; cin >> a >> b; --a, --b;
    children[a].push_back(b);
    children[b].push_back(a);
  }
  rep(i,q) {
    int p,x; cin >> p >> x; --p;
    counter[p] += x;
  }
  dfs(0);
  rep(i,n) cout << counter[i] << (i==n-1 ? "\n" : " ");
}


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

using namespace std;

typedef long long ll;

int main(){
	int n; cin >> n;
	vector<ll> a(n);
	vector<ll> done(n, false);
	for(int i=0;i<n;i++) cin >> a[i];

	multiset<int> heads;
	int colors = 0;
	for(int i=0;i<n;i++){
		// if(heads)
		auto it = heads.lower_bound(a[i]);

		// cout << (it == heads.begin()) << " | "<< (it == heads.end()) 
		//  << " | it: "<<*it << " | search: "<<a[i] << endl;

		if(heads.size() == 0 || it == heads.begin()){
			colors++;
			heads.insert(a[i]);
		}else{
			it--;
			heads.erase(it);
			heads.insert(a[i]);
		}
	}
	cout << colors << endl;

	return 0;
}

Measured memory_bytes: 6528