akhauriyash/Code-Regression huggingface dataset:
import bisect
import itertools

A,B,Q = map(int,input().split())

# 簡略化のため常に左右に存在するようにしておく
INF = 10 ** 15
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]
X = [int(input()) for _ in range(Q)]

def solve(x):
  # xの位置
  i = bisect.bisect_left(S, x)
  j = bisect.bisect_left(T, x)
  result = INF
  # どの2つを目指すのか
  for s,t in itertools.product(S[i-1:i+1], T[j-1:j+1]):
    d = min(abs(s-x),abs(t-x)) + abs(t-s)
    result = min(result,d)
  return result

for x in X:
  answer = solve(x)
  print(answer)

Measured memory_bytes: 17564
#include <iostream>

using namespace std;

struct Node
{
    Node *left, *right;
    int value;
    Node(int key = 0) : value(key) {}
};

struct List
{
    int len;
    Node *back;
    List() : len(0) {}

    void insert(int key)
    {
        if(len == 0)
        {
            back = new Node(key);
            back->left = back;
            back->right = back;
        }
        else{
            Node* node = new Node(key);
            node->right = back->right;
            back->right->left = node;
            back->right = node;
            node->left = back;
        }
        ++len;
    }

    void deleteFirst()
    {
        if(len <= 0) return;
        Node* node = back->right;
        back->right = node->right;
        node->right->left = back;
        --len;
        delete node;
    }

    void deleteLast()
    {
        if(len <= 0) return;
        Node* node = back;
        back->right->left = back->left;
        back->left->right = back->right;
        back = back->left;
        --len;
        delete node;
    }

    void deleteKey(int key)
    {
        if(len <= 0) return;
        Node* node = back->right;
        for(int i=0;i<len;++i)
        {
            if(node->value == key)
            {
                // nodeがbackだと困るので
                if(i == len - 1) back = back -> left;
                node->right->left = node->left;
                node->left->right = node->right;
                delete node;
                --len;
                break;
            }
            node = node->right;
        }
    }

    void print()
    {
        Node* node = back->right;
        for(int i=0;i<len;++i)
        {
            if(i) cout << " ";
            cout << node->value;
            node = node->right;
        }
        cout << endl;
    }
};

int main()
{
    char command[12];
    int n, key;
    List list;
    cin >> n;
    for(int i=0;i<n;++i)
    {
        cin >> command;
        if(command[0] == 'i')
        {
            cin >> key;
            list.insert(key);
        }
        else{
            if(command[6] == 'F'){
                list.deleteFirst();
            }
            else if(command[6] == 'L'){
                list.deleteLast();
            }
            else{
                cin >> key;
                list.deleteKey(key);
            }
        }
    }
    list.print();
}



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

#define ll long long
#define fore(i, n) for(i=0;i<n;i++)

int main() {
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll t;cin>>t;
	ll a, b; cin>>a>>b;
	double s=a/(double)t;
	double e=b/(double)t;
	if(ceil(s)<=floor(e))
		cout<<"OK";
	else
		cout<<"NG";
	return 0;
}

Measured memory_bytes: 3640
n = int(input())
lst = list(map(int, (input().split())))

dif_lst = []
for k, i in enumerate(lst):
    dif_lst.append(i-k-1)
l = len(dif_lst) // 2
a = sorted(dif_lst)[l]

ans = 0
for i in dif_lst:
    ans += abs((i-a))
print(ans)

Measured memory_bytes: 25284
#include <stdio.h>
#include <algorithm>

using namespace std;

int main() {
	int n, sum = 0, prv = 1000000000, nxt;
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		scanf("%d", &nxt);
		sum += min(nxt, prv);
		prv = nxt;
	}
	sum += prv;
	printf("%d\n", sum);
	return 0;
}

Measured memory_bytes: 128
n = int(input())
lis = [int(x) for x in input().split(" ")]
lis.sort(reverse=True)
lis_Alice = []
lis_Bob = []

if n % 2 == 0:
  for a in range(0, n, 2):
    lis_Alice.append(lis[a])
  for b in range(1, n+1, 2):
    lis_Bob.append(lis[b])
else:
  for a in range(0, n+1, 2):
    lis_Alice.append(lis[a])
  for b in range(1, n, 2):
    lis_Bob.append(lis[b]) 

print(sum(lis_Alice) - sum(lis_Bob))

Measured memory_bytes: 3064
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstdint>
#include <algorithm>
#include <utility>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
int N , L; cin >> N >> L;
vector<string> S(N);
rep(i,N) cin >> S[i];
sort(S.begin(),S.end());
rep(i,N) cout << S[i];
cout << endl;
}

Measured memory_bytes: 256
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fill(x,c) memset(x,c,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int SIZE = 1e6+10;
ll a[SIZE];
int main() {
	//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll n,t;
	cin>>n>>t;
	ll sum=0;
	rep(i,0,n){
		cin>>a[i];
	}
	sort(a,a+n);
	rep(i,0,n-t){
		sum+=a[i];
	}
	cout<<sum;
  	return 0;
}


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

int main() {
    vector<int> counter(5, 0);
    rep(i, 3) {
        int a, b;
        cin >> a >> b;
        counter[a]++;
        counter[b]++;
    }
    int one = 0, two = 0;
    for (int i = 1; i <= 4; i++) {
        if (counter[i] == 1) one++;
        if (counter[i] == 2) two++;
    }
    if(one == 2 && two == 2){
        puts("YES");
    }else {
        puts("NO");
    }
}

Measured memory_bytes: 3556
int_list = input().strip().split()

fee_per_sound = int(int_list[0])
takahasi_money = int(int_list[1])
satisfaction_number = int(int_list[2])

if takahasi_money >= fee_per_sound*satisfaction_number:
    print(satisfaction_number)
else:
    print(takahasi_money//fee_per_sound)

Measured memory_bytes: 2940
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<stack> 
#include<bitset>
#include<iterator>
using namespace std;


int n,m;
bitset<11111> maps[11];
int ans;


void dfs(int line){
    if(line == n){
        int tmp = 0;
        for(int i = 0 ; i < m ; i ++){
            int rownum = 0;
            for(int j = 0 ; j < n ; j ++){
                if(maps[j][i]) rownum++;
            }
            rownum = max(rownum,n-rownum);
            tmp += rownum;
        }
        ans = max(ans,tmp);
        return ;
    }
    maps[line].flip();
    dfs(line+1);
    maps[line].flip();
    dfs(line+1);

}

int main(){    
    
    while(scanf("%d%d",&n,&m) != EOF && n+m){
        ans = -1;
        for(int i = 0 ; i < n ; i ++){
            for(int j = 0 ; j < m ; j ++){
                int x;
                scanf("%d",&x);
                maps[i][j] = x;
            }
        }    
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 1200
#include <stdio.h>

int main(void)
{
	int a,b,d,r;
	double f;
scanf("%d %d",&a,&b);
d=a/b;
r=a%b;
f=1.000000*a/b;
printf("%d %d %.6lf\n",d,r,f);
	return 0;
}

Measured memory_bytes: 640
S = input()
N = len(S)

x = S[0]
y = S[1]
for i in range(2, N):
    if i % 2 == 0:
        if S[i] != x:
            break
    else:
        if S[i] != y:
            break
else:
    print("Second")
    exit()

if S[0]==S[-1]:
    if N % 2 == 0:
        print("First")
    else:
        print("Second")
else:
    if N % 2 == 0:
        print("Second")
    else:
        print("First")


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

using namespace std;

//#define FILE_IO

int N, M;
char a[505][505], red[505][505], blue[505][505];

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d\n", &N, &M);
    for(int i = 1; i <= N; i++)
        scanf("%s", a[i] + 1);
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            if(a[i][j] == '#')  a[i][j] = 1;
            else    a[i][j] = 0;
        }

    for(int i = 1; i <= N; i++)
        red[i][1] = 1, blue[i][M] = 1;
    for(int i = 1; i <= N; i++)
    {
        if(i % 2 == 0)
            for(int j = 2; j < M; j++)
                red[i][j] = 1;
        else
            for(int j = 2; j < M; j++)
                blue[i][j] = 1;
    }

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            red[i][j] |= a[i][j];
            blue[i][j] |= a[i][j];
        }

    for(int i = 1; i <= N; i++, printf("\n"))
        for(int j = 1; j <= M; j++)
            printf("%c", red[i][j] ? '#' : '.');
    printf("\n");
    for(int i = 1; i <= N; i++, printf("\n"))
        for(int j = 1; j <= M; j++)
            printf("%c", blue[i][j] ? '#' : '.');


    return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
using Graph = vector<vector<int>>;
int main() {
  double D,T,S;
  cin >> D >> T >> S;
  if(D/S <= T) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3716
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"


const int N=100005;
const int MOD=1e9+7;
 

// lower_bound - which does not compare less than val
// upper_bound - which compares greater than val
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
 
 
 int sum[N];
int main()
{
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  /* stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?)
  * do smth instead of nothing and stay organized
*/

int a,b,c,d;
cin>>a>>b>>c>>d;
while(a>0 && c>0)
{
	c=c-b;
	a=a-d;
	
}
if(c<=0)
cout<<"Yes";
else
cout<<"No";


}

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

int main(){
    ll x;
    cin >> x;
    vector<ll> ab(400);
    vector<ll> num(400);
    for(ll i = 0; i <= 200; i++){
        ab[i] = i*i*i*i*i;
        num[i] = i;
        ab[i+200] = -i*i*i*i*i;
        num[i+200] = -i;
    }

    for(int i = 0; i < 400; i++){
        for(int j = 0; j < 400; j++){
            if((ab[i] - ab[j]) == x){
                cout << num[i] << ' ' << num[j] << endl;
                //cout << i << ' ' << j << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 3628
import java.util.Scanner;
import java.lang.String;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int[] counter = new int[127];
        while (sc.hasNext()) {
            String str = sc.nextLine().toLowerCase();
            for (int i = 0; i < str.length(); i++) {
                counter[str.charAt(i)]++;
            }
        }
        for (char i = 'a'; i <= 'z'; i++) {
            System.out.println(i + " : " + counter[i]);
        }
    }
}
//答え(sc.nextline.toLowerCase();のような関数が連続するところの理解はできるが実装する発想が難しい。。。


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

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debugF(ostream &os) {os << endl;}
template <typename Head, typename... Tail>
void debugF(ostream &os, Head H, Tail... T) { os << " " << H; debugF(os, T...); }
#define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debugF(cout, __VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); os << (i>0 ? " ":"") << v[i++]); return os;}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, i;
    cin >> n;
    int ans = 0;
    for(i=1;i<=n;i++){
        int a; cin >> a;
        if(i%2 == 1 && a%2 == 1) ans++;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3624
h,w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
s = []
l = []
for x in range(n):
  s += [x+1]*a[x]
for i in range(h):
  l.append(s[w*i:w*(i+1)])
  if i%2:
    l[i] = l[i][::-1]
for x in l:
  print(" ".join(map(str,x)))

Measured memory_bytes: 3572
#include <bits/stdc++.h> 
using namespace std;
int comp(const void* a, const void* b)  
{ return *(int*)a > *(int*)b ; }  
int findNumberOfTriangles(int arr[], int n)  
{  
    qsort(arr, n, sizeof( arr[0] ), comp);
    int count = 0;
    for (int i = 0; i < n - 2; ++i)  
    {
        int k = i + 2;  
        for (int j = i + 1; j < n; ++j)  
        {
            while (k < n && arr[i] + arr[j] > arr[k])  
            k++; 
            if(k > j)  
            count += k - j - 1;  
        }  
    }  
  
    return count;  
}  

int main()  
{  
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++)
    	cin >> arr[i];
    int size = n;
  
    cout << findNumberOfTriangles( arr, size ) << endl;  
  
    return 0;  
}  

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define ld long double
#define forever while(true)
int vx[13] = { -3,-2,-1,0,0,0,0,0,0,0,1,2,3 };
int vy[13] = { 0,0,0,0,-3,-2,-1,1,2,3,0,0,0 };
char a[8][8];
int blow(int x, int y)
{
	a[x][y] = '0';
	rep(i, 13) {
		int nextx = x + vx[i];
		int nexty = y + vy[i];
		if (nextx < 0 || 8 <= nextx || nexty < 0 || 8 <= nexty) {
			continue;
		}
		if (a[nextx][nexty] == '1')
		{
			int u = blow(nextx, nexty);
		}
		a[nextx][nexty] = '0';
	}
	return 0;
}
int main() {
	int n;
	cin >> n;
	rep(i, n) {
		//string muda;
		//cin >> muda;

		rep(i1, 8) {
			rep(i2, 8) {
				cin >> a[i2][i1];
			}
		}
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		cout << "Data " << i + 1 << ":" << endl;
		int u = blow(x, y);
		for (int k = 0; k < 8; k++)
		{
			for (int j = 0; j < 8; j++) {
				cout << a[j][k];
			}
			cout << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 2988
import java.util.Scanner;

/**
 * Created by sd on 2016/11/22.
 */
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int a[] = new int[N];
        for(int I=0;I<N;I++){
            a[I] = sc.nextInt();
        }

        int count = 0;
        boolean flag = true;
        while (flag){
            flag = false;
            for (int j=N-1; j>=1; j--){
                if(a[j] < a[j-1]){
                    int t = a[j];
                    a[j] = a[j-1];
                    a[j-1] = t;
                    flag = true;
                    count ++;
                }
            }
        }
        for(int ii=0; ii<N-1; ii++){
            System.out.print(a[ii]+" ");
        }
        System.out.println(a[N-1]);
        System.out.println(count);
    }
}

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

int main(){
    string s;
    cin >> s;
    int L,r;
    int l=s.size();
    for (int i=0;i<l;i++){
        if (s[i]=='A'){
            L = i;
            break;
        }
    }
    for (int j=l-1;j>=0;j--){
        if (s[j]=='Z'){
            r = j;
            break;
        }
    }
    cout << r-L+1 << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
using namespace std;

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




Measured memory_bytes: 3124
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstring>
#include <iomanip>
#include <utility>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e5 + 5;
const int D = 15;

int n, m, q;
vector<int> g[N];
int v[N], d[N], c[N];
bool vis[N][D];
int ans[N];

void dfs(int node, int dist, int color) {
	vis[node][dist] = true;
	if (ans[node] == 0) ans[node] = color;
	if (dist == 0) return;
	for (int v : g[node]) {
		if (vis[v][dist - 1]) continue;
		dfs(v, dist - 1, color);
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	cin >> n >> m;

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

	cin >> q;

	for (int i = 0; i < q; i++) {
		cin >> v[i] >> d[i] >> c[i];
	}

	for (int i = q - 1; i >= 0; i--) {
		if(!vis[v[i]][d[i]]) dfs(v[i], d[i], c[i]);
	}

	for (int i = 1; i <= n; i++) cout << ans[i] << '\n';

	return 0;
}

Measured memory_bytes: 9592
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
 
int main() {
	string str;
	int n;
	while(1){
		cin >> n;
		if(n==0) break;
		int sum=0;
		int num[n];
		for(int i=0; i<n; i++){
			int t;
			cin >> t;
			sum += t;
			num[i] = t;
		}
		double avg = 1.0*sum/n;
		double ans =0;
		for(int i=0; i<n; i++){
			ans += pow(num[i]-avg,2);
		}
		ans = sqrt(ans/n);
		printf("%lf\n", ans);
	}
	return 0;
}


Measured memory_bytes: 3212
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

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

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
const int mod = 1000000007;
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")



/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}
int main() { 
  int n,k,s;cin>>n>>k>>s;
  if(s == (int)1e9){
    int i = 0;
    for(; k > i; i++){
      cout << s;
      if(i+1 != n)cout << " ";
    }
    for(; n > i; i++){
      cout << s-1;
      if(i+1 != n)cout << " ";
    }
    cout << endl;
  }else{
    int i = 0;
    for(; k > i; i++){
      cout << s;
      if(i+1 != n)cout << " ";
    }
    for(; n > i; i++){
      cout << s+1;
      if(i+1 != n)cout << " ";
    }
    cout << endl;
  }
}

Measured memory_bytes: 1280
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    XYR = [[xs, ys, 0], [xt, yt, 0]]
    for _ in range(n):
        x, y, r = map(int, input().split())
        XYR.append([x, y, r])

    cost = [[0] * (n + 2) for _ in range(n + 2)]
    for i in range(n + 2):
        x1, y1, r1 = XYR[i]
        for j in range(n + 2):
            x2, y2, r2 = XYR[j]
            dist = max(0, pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5) - (r1 + r2))
            cost[i][j] = cost[j][i] = dist

    def dijkstra(s):
        # 始点sから各頂点への最短距離
        # n:頂点数, cost[u][v]:辺uvのコスト(存在しないときはinf)
        d = [f_inf] * (n + 2)
        used = [False] * (n + 2)
        d[s] = 0

        while True:
            v = -1
            # まだ使われてない頂点の中から最小の距離のものを探す
            for k in range(n + 2):
                if (not used[k]) and (v == -1):
                    v = k
                elif (not used[k]) and d[k] < d[v]:
                    v = k
            if v == -1:
                break
            used[v] = True

            for m in range(n + 2):
                d[m] = min(d[m], d[v] + cost[v][m])
        return d

    res = dijkstra(0)
    print(res[1])


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 91356
#include<stdio.h>
int max(int a,int b)
{
	if(a>b)
	  return a;
	else
	  return b;
}
int min(int a,int b)
{
	if(a<b)
	  return a;
	else
	  return b;
}
int main()
{
	int w,h,n;
	scanf("%d %d %d",&w,&h,&n);
	int i;
	int x,y,a;
	int xmax,xmin,ymax,ymin;
	xmin=ymin=0;
	xmax=w;
	ymax=h;
	for(i=0;i<n;i++)
	{
		scanf("%d %d %d",&x,&y,&a);
		if(a==1)xmin=max(xmin,x);
		if(a==2)xmax=min(xmax,x);
		if(a==3)ymin=max(ymin,y);
		if(a==4)ymax=min(ymax,y);
	}
	x=xmax-xmin;
	y=ymax-ymin;
	if(x<0 || y<0)
	{
		printf("0\n");
		return 0;
	}
	else
	{
		printf("%d\n",x*y);
		return 0;
	}
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
  int a,b,c,d;
  scanf("%d%d%d%d" , &a , &b , &c , &d );
  if(a+b>c+d)printf("Left\n");
  else if(a+b==c+d)printf("Balanced\n");
  else printf("Right\n");
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
int D, N, a[111], e[111], r[111], dp[111][111];
int main() {
	while (scanf("%d%d", &D, &N), D | N) {
		for (int i = 0; i < N; i++) scanf("%d%d%d", a + i, e + i, r + i);
		int maxr = *max_element(r, r + N);
		for (int i = 0; i <= D; i++) fill(dp[i], dp[i] + maxr + 1, 999999999);
		dp[0][0] = 0;
		for (int i = 0; i < D; i++) {
			for (int j = 0; j <= maxr; j++) {
				for (int k = 0; k < N; k++) {
					if (j < r[k]) continue;
					int p = min(j + e[k], maxr), q = min(i + a[k], D);
					dp[q][p] = min(dp[q][p], dp[i][j] + 1);
				}
			}
		}
		int ret = *min_element(dp[D], dp[D] + maxr + 1);
		if (ret == 999999999) puts("NA");
		else printf("%d\n", ret);
	}
}

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

#define REP(i,n) for(int i=0;i<n;++i)
#define RREP(i,n) for(int i=n-1;i>=0;--i)
#define FOR(i,m,n) for(int i=m;i<n;++i)
#define RFOR(i,m,n) for(int i=m-1;i>=n;--i)
#define ALL(v) v.begin(),v.end()
#define PB(a) push_back(a)
#define INF 1000000001
#define MOD 1000000007

const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };

using namespace std;


#define MAX_N 246913
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	vector<bool> b(246913, true);
	b[0] = false;
	b[1] = false;
	FOR(i, 2, sqrt(MAX_N)) {
		if (b[i]) for (int j = i + i;j< MAX_N;j += i) b[j] = false;
	}
	while (1) {
		int n;
		cin >> n;
		if (!n) break;
		int cnt = 0;
		FOR(i, n + 1, 2 * n + 1) {
			if (b[i]) cnt++;
		}
		cout << cnt << endl;

	}

	return 0; 
}

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

int main() {
  int N;
  scanf("%d", &N);
  std::string x(N, ' ');
  scanf("%s", &x[0], x.size());
  if (x.length() % 2 != 0) {
    printf("No");
    return 0;
  }
  for (int i = 0; i < N / 2; i++) {
    if (x[i] != x[N / 2 + i]) {
      printf("No");
      return 0;
    }
  }
  printf("Yes");
}


Measured memory_bytes: 256
var a,b,c,d,ans,ai,bi,x,y,w   :int64;

begin
  readln(a,b,c,d);
  
  if (c>0)and(d>0) then begin
    x:=c; y:=d;
    while x<>0 do begin
      w:=y mod x; y:=x; x:=w
    end;
  end;
  
  
  ai:=(a-1)div c + (a-1)div d - (a-1)div (c*d div y);
  bi:=b div c + b div d - b div (c*d div y);
  ans:= b-a+1 - (bi-ai);
  writeln(ans)
end.

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()
#define VEC(TYPE, A, NAME, INIT) vector<TYPE> NAME(A, INIT)
#define VEC2(TYPE, A, B, NAME, INIT) vector<vector<TYPE>> NAME(A, vector<TYPE>(B, (INIT)))

int main()
{
	string s;
	cin >> s;
	list<int> v;
	REP( i, s.size() ) v.push_back( s[i] );

	ull ans = 0;
	auto it = v.begin();
	while( ++it != v.end() )
	{
		if( *it != *(--it) )
		{
			it = v.erase( it );
			it = v.erase( it );
			if( it != v.begin() ) --it;
			ans += 2;
		}
		else ++it;
	}

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

Measured memory_bytes: 3456
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main(void) {

	lli a, b;
	cin >> a >> b;

	if (a > 9 || b > 9)
		cout << "-1" << endl;
	else
		cout << a * b << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int pnt[maxn];
vector<int>edge[maxn];
int q[maxn], head, tail;
int main(){
  	int n,m,u,v;
  	cin>>n>>m;
  	for (int i=1;i<=m;i++){
      	cin>>u>>v;
      	edge[u].push_back(v);
      	edge[v].push_back(u);
    }
  	head = 1; tail = 1;
  	q[1] = 1;
  	while (head <= tail){
    	int x = q[head++];
      	for (int i=0,sz=edge[x].size();i<sz;i++){
        	int to = edge[x][i];
          	if (to == 1 || pnt[to] ) continue;
          	q[++tail] = to;
          	pnt[to] = x;
        }
    }
  	int cnt = 1;
  	for (int i=2;i<=n;i++) if (pnt[i]) cnt++;
  	if (cnt == n){
    	cout<<"Yes"<<endl;
      	for (int i=2;i<=n;i++) cout<<pnt[i]<<endl;
    }
  	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 13060
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Diagnostics;
using static System.Console;
using static System.Math;


namespace AtCoder
{
    class AtCoderrrrr
    {
        static void Main(string[] args)
        {
            string s = ReadLine();
            int a = int.Parse(s[0].ToString());
            int b = int.Parse(s[1].ToString());
            int c = int.Parse(s[2].ToString());
            int d = int.Parse(s[3].ToString());
            if (a+b+c+d == 7)
            {
                WriteLine(a + "+" + b + "+" + c + "+" + d + "=7");
            }
            else if (a+b+c-d == 7)
            {
                WriteLine(a + "+" + b + "+" + c + "-" + d + "=7");
            }
            else if (a + b - c + d == 7)
            {
                WriteLine(a + "+" + b + "-" + c + "+" + d + "=7");
            }
            else if (a - b + c + d == 7)
            {
                WriteLine(a + "-" + b + "+" + c + "+" + d + "=7");
            }
            else if (a+b-c-d == 7)
            {
                WriteLine(a + "+" + b + "-" + c + "-" + d + "=7");
            }
            else if (a-b+c-d == 7)
            {
                WriteLine(a + "-" + b + "+" + c + "-" + d + "=7");
            }
            else if (a-b-c+d == 7)
            {
                WriteLine(a + "-" + b + "-" + c + "+" + d + "=7");
            }
            else
            {
                WriteLine(a + "-" + b + "-" + c + "-" + d + "=7");
            }
        }
        
    }
}


Measured memory_bytes: 11220
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


a, b, c, d = ints()
print(max(a * c, a * d, b * c, b * d))


Measured memory_bytes: 68116
# 切り方は3通りです

# 1. 縦または横に大体三等分する
# 2. 縦または横に三分の一未満で最大切り取ったあと、
#   横または縦に大体二等分する
# 3. 縦または横に三分の一以上で最大切り取ったあと、
#   横または縦に大体二等分する


H, W = map(int, input().split())

if (H%3)*(W%3)==0:
  print(0)
else:
  d1 = min(H, W)
  ah = H//3
  h = H-ah
  d2 = abs(((W+1)//2)*h - ah*W)
  aw = W//3
  w = W-aw
  d3 = abs(((H+1)//2)*w - aw*H)
  ah = (H+2)//3
  h = H-ah
  d4 = abs((W//2)*h - ah*W)
  aw = (W+2)//3
  w = W-aw
  d5 = abs((H//2)*w - aw*H)

  print(min(d1,d2,d3,d4,d5))

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

// AtCoder
#include <atcoder/all>
using namespace atcoder;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...)
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fls(x) (64 - __builtin_clzll(x))
#define pcnt(x) __builtin_popcountll(x)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q; cin >> n >> q;
    dsu uf(n);
    rep (_, q) {
        int c, u, v; cin >> c >> u >> v;
        if (c == 0) uf.merge(u, v);
        else cout << uf.same(u, v) << "\n";
    }
    return 0;
}

Measured memory_bytes: 4040
let () =
  Scanf.scanf "%1s%1s%1s\n" @@ fun s1 s2 s3 ->
  Printf.printf "%d\n"
    (if s1 = "S" && s2 = "S" && s3 = "S" then 0 
     else if s1 = "R" && s2 = "R" && s3 = "R" then 3
     else if (s1 = "R" && s2 = "R") || (s2 = "R" && s3 = "R") then 2 else 1)

Measured memory_bytes: 3812
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
# include <cstdlib>
# include <tuple>
# include <array>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2147483647;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr double HDINF = 50000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
# define ALL(x)      (x).begin(),(x).end()
# define UNIQUE(c)   (c).erase(unique(ALL((c))),(c).end())
# define LOWER(s)    transform(ALL((maze)),(maze).begin(),TL<char>)
# define UPPER(s)    transform(ALL((maze)),(maze).begin(),TU<char>)
# define FOR(i,a,b)  for(LL i=(a);i<(b);i++)
# define RFOR(i,a,b) for(LL i=(a);i>=(b);i--)
# define REP(i,n)    FOR(i,0,n)
# define INIT        std::ios::sync_with_stdio(false);std::cin.tie(0)

int n;
string maze[660];
bool calc(int moveh) {
	REP(i, n)for (int j = i + 1; j < n; j++) {
		if (maze[i+moveh][j] != maze[j+moveh][i])return false;
	}
	return true;
}

int main(){
	cin >> n;
	LL ans = 0;
	REP(i, n) {
		cin >> maze[i];
	}
	REP(i, n) {
		maze[n + i] = maze[i];
	}
	REP(num, n) {
		if (calc(num))ans += n;
		//cout <<"       "<< ans << endl;
	}
	cout << ans << endl;
	//system("pause");
}

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

using namespace std;

int V, E, S, G1, G2, B1, B2, C;

vector<vector<int> > G;

vector<vector<int> > R;

void Shortest(int s, int mode, int rev)
{
	vector<bool> u(V, false);
	
	R[mode][s] = 0;

	while (true)
	{
		int v = -1, c = 99999999;

		for (int i = 0; i < V; i++)
		{
			if (!u[i] && R[mode][i] < c)
			{
				c = R[mode][i]; v = i;
			}
		}

		if (c == 99999999) { break; }

		u[v] = true;

		for (int i = 0; i < V; i++)
		{
			if (!u[i])
			{
				if (R[mode][i] > R[mode][v] + (rev ? G[i][v] : G[v][i]))
				{
					R[mode][i] = R[mode][v] + (rev ? G[i][v] : G[v][i]);
				}
			}
		}
	}
}

int main()
{
	while (true)
	{
		cin >> V >> E >> S >> G1 >> G2;

		if (V == 0) { break; }

		G = vector<vector<int> >(V, vector<int>(V, 99999999));

		for (int i = 0; i < E; i++)
		{
			cin >> B1 >> B2 >> C;

			G[B1 - 1][B2 - 1] = C;
		}
		
		R = vector<vector<int> >(3, vector<int>(V, 99999999));

		Shortest(S - 1, 0, 0);
		Shortest(G1 - 1, 1, 1);
		Shortest(G2 - 1, 2, 1);

		int ret = 299999997;

		for (int i = 0; i < V; i++)
		{
			ret = min(ret, R[0][i] + R[1][i] + R[2][i]);
		}

		cout << ret << endl;
	}

	return 0;
}

Measured memory_bytes: 3248
S = input()

r = 0
l = 0
ans = 0
val = 0
for i in range(len(S)):
    if(S[i] == "<"):
        if(l == 1):
            r = 1
            if(val > l):
                ans += val
                val = 0
                l = 0
            else:
                ans += l
                l = 0
        elif(l > 1):
            if(val > l):
                ans += (l*(l+1))//2+(val-l)
                l = 0
                r = 1
                val = 0
            else:
                ans += (l*(l+1))//2
                l = 0
                r = 1
                val = 0
        else:
            r += 1
    else:
        if(r):
            ans += (r*(r-1))//2
            val = r
            l = 1
            r = 0
        else:
            l += 1
if(l):
    if(l == 1):
        if(val > l):
            ans += val
        else:
            ans += l
    else:
        if(val > l):
            ans += (l*(l+1))//2+(val-l)
        else:
            ans += (l*(l+1))//2
else:
    ans += (r*(r+1))//2
print(ans)

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

int main()
{
	long long int n;
	cin >> n;
	long long int ans = 1;
	long long int in[100000];
	for (int i = 0; i < n; ++i)
	{
		cin >> in[i];
	}
	sort(in, in+n);
	for (int i = 0; i < n; ++i)
	{
		if ((double)log10(ans) + (double)log10(in[i]) > 18 || ans * in[i] >= 1000000000000000001)
		{
			cout << -1 << endl;
			return 0;
		}
		ans *= in[i];
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 4728
#include <stdio.h>
  
#define N 500001
#define S 10000000333
  
void Merge(int*,int, int, int);
void Merge_Sort(int*,int, int);
  
int c = 0;
main(){
  
int n,i,A[N];
  
scanf("%d",&n);
  
for(i = 0; i < n ; i++) scanf("%d",&A[i]);
  
Merge_Sort(A,0,n);

for(i = 0;i < n;i++){
    printf("%d",A[i]);
    if(i < n-1){
      printf(" ");
    }
  }
     
  printf("\n%d\n",c);
   
  return 0;
     
} 
 
  
  
void Merge_Sort(int* A,int left, int right){
  int mid;
  if(left+1 < right){
    mid = (left + right) / 2;
    Merge_Sort(A,left, mid);
    Merge_Sort(A,mid, right);
    Merge(A,left, mid, right);
  }
  }
  
void Merge(int* A,int left,int mid,int right){
  int n1,n2;
  int i,j,k;
  int L[N],R[N];
     
  n1 = mid - left;
  n2 = right - mid;
     
  for(i = 0; i < n1; i ++){
    L[i] = A[left + i];
  }
  for(i = 0; i < n2; i ++){
    R[i] = A[mid + i];
  }
     
  L[n1] = S;
  R[n2] = S;
     
  i = 0;
  j = 0;
    
  for (k = left; k <= right-1; k ++)
    {
      c++;
      if (L[i] <= R[j]){
    A[k] = L[i];
    i++;
      }else{
    A[k] = R[j];
    j++;
      }
    }
}

Measured memory_bytes: 5492
import Control.Applicative
import Control.Monad
import Data.Set (Set)
import qualified Data.Set as S

main :: IO ()
main = do
  s <- getLine
  unless (s == "0") $ do
    putStrLn $ solve s
    main

solve :: String -> String
solve s = loop 0 (S.singleton s) (S.singleton s)
  where
    ln = length s
    goal = S.fromList $ map (replicate ln) "rgb"
    loop c st hst
      | S.null st = "NA"
      | not (S.null (S.intersection goal st)) = show c
      | otherwise = let nst = S.foldl' (\x s -> S.union x $ S.fromList $ do
                                           s' <- changeColor ln s
                                           guard $ S.notMember s' hst
                                           return s'
                                       ) S.empty st
                    in loop (c+1) nst (S.union hst nst)

changeColor :: Int -> String -> [String]
changeColor n s = do
  i <- [0 .. n-2]
  let (s1, c1:c2:s2) = splitAt i s
  guard $ c1 /= c2
  case (c1, c2) of
   ('r', 'g') -> return $ s1 ++ "bb" ++ s2
   ('g', 'b') -> return $ s1 ++ "rr" ++ s2
   ('b', 'r') -> return $ s1 ++ "gg" ++ s2
   ('g', 'r') -> return $ s1 ++ "bb" ++ s2
   ('b', 'g') -> return $ s1 ++ "rr" ++ s2
   ('r', 'b') -> return $ s1 ++ "gg" ++ s2



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

// Begin {{{
using namespace std;
#define all(x) x.begin(), x.end()
#define rep(i, n) for (i64 i = 0; i < (n); ++i)
#define reps(i, b, e) for (i64 i = (b); i <= (e); ++i)
#define repr(i, b, e) for (i64 i = (b); i >= (e); --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
inline i64 sigma(i64 n) { return n * (1 + n) >> 1; }
inline i64 updiv(i64 n, i64 d) { return (n + d - 1) / d; }
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;
#ifndef DEBUG
#define dump(...)
#endif

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
  cin >> head;
  input(forward<Tail>(tail)...);
}

inline void outs() { cout << "\n"; }
template <class Head, class... Tail>
inline void outs(Head&& head, Tail&&... tail) {
  cout << head << (sizeof...(tail) ? " " : "");
  outs(forward<Tail>(tail)...);
}

template <class T>
inline void outs(vector<T> &vec) { for (auto &e : vec) cout << e << " \n"[&e == &vec.back()]; }

template <class T>
inline void outs(vector<vector<T>> &df) { for (auto &vec : df) outs(vec); }

inline void outl() { cout << "\n"; }
template <class Head, class... Tail>
inline void outl(Head&& head, Tail&&... tail) {
  cout << head << (sizeof...(tail) ? "\n" : "");
  outl(forward<Tail>(tail)...);
}

template <class T>
inline void outl(vector<T> &vec) { for (auto &e : vec) cout << e << "\n"; }

inline void outn() {}
template <class Head, class... Tail>
inline void outn(Head&& head, Tail&&... tail) {
  cout << head;
  outn(forward<Tail>(tail)...);
}

template <class T>
inline void outn(vector<T> &vec) { for (auto &e : vec) cout << e; }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
  return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
  return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}
// }}} End

const int MAX = int(1e5);

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

  var(int, N);

  vector<int> coin;
  coin.emplace_back(1);

  int i = 1;
  while (true) {
    i64 norm = pow(6, i);
    if (norm >= MAX) break;
    coin.emplace_back(norm);
    ++i;
  }

  i = 1;
  while (true) {
    i64 norm = pow(9, i);
    if (norm >= MAX) break;
    coin.emplace_back(norm);
    ++i;
  }

  sort(all(coin));

  auto dp = make_v(0, coin.size() + 5, N + 5);

  for (int j = 0; j <= N; ++j) dp[0][j] = j;

  for (int i = 0; i < coin.size(); ++i) {
    for (int j = 0; j <= N; ++j) {
      dp[i+1][j] = dp[i][j];
      if (j >= coin[i]) chmin(dp[i+1][j], dp[i+1][j-coin[i]] + 1);
    }
  }

  outl(dp[coin.size()][N]);

  return 0;
}


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

int main()
{
    long long ningen;
    cin >> ningen;

    long long kiriagewarizan(long long n,long long m);
    
    long long n[5];
    for (int j = 0; j<5 ; j++){
        cin >> n[j];
        if (n[0] > n[j]){n[0]=n[j];}
    }

    cout << 4 + kiriagewarizan(ningen,n[0]);

}

long long kiriagewarizan(long long n,long long m){
    long long kotae = n/m;
    if (n%m != 0){kotae++;}
    return kotae;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define ll long long
#define sort(vec) sort((vec).begin(),(vec).end());
#define rever(vec) reverse((vec).begin(),(vec).end());
#define cout0 cout<<"0"<<endl

using namespace std;

int main() {
  int W,H,N;
  cin>>W>>H>>N;
  int w=0;
  int h=0;
  for(int i=0;i<N;i++) {
    int x,y,a;
    cin>>x>>y>>a;
    if(a==1) {
      if(w<=x&&x<=W) {
        w=x;
        if((W-w)==0) {
          cout0;
          return 0;
        }
      }
      else if(x>W) {
        cout<<"0"<<endl;
        return 0;
      }
    }
    else if(a==2) {
      if(w<=x&&x<=W) {
        W=x;
        if((W-w)==0) {
          cout0;
          return 0;
        }
      }
      else if(x<w){
        cout0;
        return 0;
      }
    }
    else if(a==3) {
      if(h<=y&&y<=H) {
        h=y;
        if((H-h)==0) {
          cout0;
          return 0;
        }
      }
    }
    else {
      if(h<=y&&y<=H) {
        H=y;
        if((H-h)==0) {
          cout0;
          return 0;
        }
      }
    }
  }
  cout<<(W-w)*(H-h)<<endl;
}

Measured memory_bytes: 256
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(ll i##_len=(n) ,i=i##_len-1;i>=0;--i)
#define repi(i,a,b) for(ll i=ll(a);i<=ll(b);++i)
#define ALL(f,x,...) ([&](decltype((x)) xxxx) { return (f)(begin(xxxx), end(xxxx), ## __VA_ARGS__); })(x)
#define lim 1000000007ll
#define Yes(flag) cout<<((flag)? "Yes":"No");
#define YES(flag) cout<<((flag)? "YES":"NO");
#define MSG(msg1,msg2,flag) cout<<((flag)? msg1:msg2);

#include<bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = std::pair<ll,ll>;
using namespace std;
template<class T>T 
chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T>T 
chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template <class T> T 
gcd(T a, T b){if (a < b) {a ^= b;b ^= a;a ^= b;} return b ? gcd(b, a % b) : a;}
template <class T> T 
lcm(T a, T b){return a * b / gcd(a, b);}
vector<char> 
string_to_vector_char(const string& input){vector<char> out(input.length());rep(i,input.length()){out[i]=input[i];}return out;}
template <class T> map<T,int> 
count_same_elements(const vector<T>& v){map<T,int>cmap; for_each(v.begin(),v.end(),[&cmap](auto x){cmap[x]++;}); return cmap; }
template<class A,class B> vector<B> 
mapf(const vector<A>& v,const function<B(A)>& func){vector<B> v_(v.size());rep(i,v.size()){ v_[i]=func(v[i]); }return v_;}
template<class A,class B> vector<B> 
adjacent_map(const vector<A>& v,const function<B(A,A)>& func){vector<B> v_(v.size()-1);rep(i,v.size()-1){ v_[i]=func(v[i+1],v[i]); }return v_;}
template<class A> bool
all_of(const vector<A>& v){bool flag=true;rep(i,v.size()){ if(v[i]<1){flag=false;}; }return flag;}
template<class A> bool
any_of(const vector<A>& v){bool flag=false;rep(i,v.size()){ if(v[i]>0){flag=true; break;}; }return flag;}
template<class A> bool
none_of(const vector<A>& v){bool flag=true;rep(i,v.size()){ if(v[i]>0){flag=false;}; }return flag;}
template<class T>
void scan_vector(long long size,vector<T>& vector){
    vector.resize(size);
    for(long long i=0;i<size;++i){
        cin>>vector[i];
    }
}

int n,c,m;
vector<int> a,b;
void input(){
    cin>>n>>m>>c;
    scan_vector(m,b);
}
void src(){
    int ans=0;
    rep(i,n){
        scan_vector(m,a);
        int sum=c;
        rep(j,m){
            sum+=a[j]*b[j];
        }
        if(sum>0) ans++;
    }
    cout<<ans;
}   

int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
 //   ifstream in( argv[1] ); cin.rdbuf(in.rdbuf());
    input();
    src();    
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    int max_num = (n-1)*(n-2)/2;
    if(k > max_num){
        cout << -1 << endl;
        return 0;
    }
    vector<P> ans;
    for(int i = 2; i <= n; i++){
        ans.emplace_back(1, i);
    }
    for(int i = 2; i <= n; i++){
        for(int j = 2; j < i; j++){
            ans.emplace_back(i, j);
            max_num--;
            if(max_num == k) break;
        }
        if(max_num == k) break;
    }
    cout << ans.size() << endl;
    for(auto &p : ans){
        cout << p.first << " " << p.second << endl;
    }
    return 0;
}


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

int main() {
  
  int N ;
  cin >> N;
  vector<int> A(N) ;
  rep(i,N) cin >> A.at(i) ;
  int ans  = 0 ;
  for(int j = 0 ; j < N - 1 ; j++ ){
    for(int k = j + 1 ; k < N ; k++ ){
      ans += A.at(j) * A.at(k) ;
    }
  }
  cout << ans << endl ;
}

Measured memory_bytes: 256