akhauriyash/Code-Regression huggingface dataset:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for i in range(N)]
    for i in range(1, N):
        Edge[i].append((0, i - 1))
    for _ in range(M):
        L, R, C = map(int, input().split())
        Edge[L-1].append((C, R-1))
    
    Dist = [-1] * N
    Q = []
    heapify(Q)
    heappush(Q, (0, 0))
    while Q:
        nowcost, nownode = heappop(Q)
        if Dist[nownode] == -1:
            Dist[nownode] = nowcost
            for addcost, nextnode in Edge[nownode]:
                if Dist[nextnode] == -1:
                    heappush(Q, (nowcost + addcost, nextnode))
    print(Dist[N-1])

    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 45484
import java.util.Scanner;

public class Main {
	static int intN =0;
	static int sosuCnt =0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String n = sc.nextLine();
		String[] h = sc.nextLine().split(" ");

		int intN = Integer.parseInt(n);

		int max = 0;
		int cnt=0;
		for (int i = 0;i < h.length-1;i++) {
			if (Integer.parseInt(h[i]) >= Integer.parseInt(h[i+1])) {
				cnt++;
			} else {
				if (max < cnt) {
					max=cnt;
				}
				cnt=0;
			}
		}
		if (max < cnt) {
			max=cnt;
		}


		System.out.println(max);
	}
}

Measured memory_bytes: 50540
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define br cout << endl;
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}

// 0 false, 1 true 
// stringの数字をint型にしてアスキーコードになったら -48する
// 切り上げ　ceil(a)


int main() {
    ll h, a;
    cin >> h >> a;
    if(h % a == 0){
        cout << h /a << endl;
    }else{
        cout << (h / a) + 1 << endl;
    }


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const LL mod=1000000007;
const int INF=1e7;
const LL LINF= 1LL << 62;

LL GCD(LL x,LL y){
    if(x%y==0) return y;
    return GCD(y,x%y);
}

int main(){
    int N;
    LL K;
    cin >> N >> K;
    LL a[N];
    LL maxi=0;
    for(int i=0;i<N;i++){
        cin >> a[i];
        maxi=max(maxi,a[i]);
    }
    LL k=a[0];
    for(int i=0;i<N;i++){
        k=GCD(k,a[i]);
    }
    if(K%k==0&&K<=maxi) puts("POSSIBLE");
    else puts("IMPOSSIBLE");
    return 0;
}



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

int main()
{
  int W,H,x,y,r;
  
  cin >> W >> H >> x >> y >> r;
  
  if((r<=x) && (r<=y) && ((x+r)<=W) && ((y+r)<=H)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  return 0;
} 

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long int

int32_t main()
{
    int N,M;
    cin>>N>>M;
    string A[N];
    
    for(int i=0;i<N;i++)
    {
        string x;
        cin>>x;
        A[i]=x;
    }

    int dp[N][M];
    
    dp[N-1][M-1]=1;
    
    for(int i=N-2;i>=0;i--)
        if(A[i][M-1]=='.')
            dp[i][M-1]=dp[i+1][M-1];
        else
            dp[i][M-1]=0;
            
    for(int i=M-2;i>=0;i--)
        if(A[N-1][i]=='.')
            dp[N-1][i]=dp[N-1][i+1];
        else
            dp[N-1][i]=0;
            
    for(int i=N-2;i>=0;i--)
        for(int j=M-2;j>=0;j--)
            if(A[i][j]=='.')
                dp[i][j]=(dp[i+1][j]%mod+dp[i][j+1]%mod)%mod;
            else
                dp[i][j]=0;
                
    cout<<dp[0][0]%mod;
    return 0;
}

Measured memory_bytes: 12448
#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>>;

VV<int> g;
V<int> vis, col;

void dfs(int p, int c) {
    if (vis[p]) return;
    vis[p] = true;
    col[p] = c;
    for (int d: g[p]) {
        dfs(d, 1-c);
    }
}

void mark() {
    int n = int(g.size());
    vis = V<int>(n);
    col = V<int>(n);
    for (int i = 0; i < n; i++) {
        dfs(i, 0);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20);

    int n;
    V<int> dv(2);
    cin >> n >> dv[0] >> dv[1];
    int base = 1;
    VV<int> col2(2*n, V<int>(2*n));
    using P = pair<int, int>;
    for (int d: dv) {
        V<P> v;
        for (int h = -2*n; h <= 2*n; h++) {
            int rm = d - h*h;
            if (rm < 0) continue;
            int r = int(sqrt(rm) + 1e-9);
            if (h*h + r*r != d) continue;
            v.push_back(P(h, r));
            v.push_back(P(-h, r));
            v.push_back(P(h, -r));
            v.push_back(P(-h, -r));
        }
        sort(begin(v), end(v));
        v.erase(unique(begin(v), end(v)), end(v));
        g = VV<int>(4*n*n);
        for (int h = 0; h < 2*n; h++) {
            for (int r = 0; r < 2*n; r++) {
                for (auto p: v) {
                    int nh = h + p.first, nr = r + p.second;
                    if (!(0 <= nh && nh < 2*n && 0 <= nr && nr < 2*n)) continue;
                    int id1 = h*(2*n) + r;
                    int id2 = nh*(2*n) + nr;
                    g[id1].push_back(id2);
                }
            }
        }
        mark();
        for (int h = 0; h < 2*n; h++) {
            for (int r = 0; r < 2*n; r++) {
                int id = h*(2*n) + r;
                if (col[id]) col2[h][r] += base;
            }
        }
        base *= 2;
    }

    VV<P> pots(4);
    for (int h = 0; h < 2*n; h++) {
        for (int r = 0; r < 2*n; r++) {
            pots[col2[h][r]].push_back(P(h, r));
        }
    }
    sort(begin(pots), end(pots), [&](const V<P> &l, const V<P> &r){
        return l.size() > r.size();
    });
    auto ans = pots[0];
    assert(ans.size() >= n*n);
    ans.resize(n*n);
    for (auto p: ans) {
        cout << p.first << " " << p.second << '\n';
    }
    return 0;
}


Measured memory_bytes: 80256
#include <iostream>
#include <string>

using namespace std;

int main(){
  string taro, hana;
  int n, tp=0, hp=0;

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> taro >> hana;
    if(taro == hana){
      tp++; hp++;
    }
    else if(taro < hana){
      hp += 3;
    }
    else{
      tp += 3;
    }
  }

  cout << tp << " " << hp << endl;

  return 0;
}



Measured memory_bytes: 3160
import itertools
import math
d, g = map(int, input().split())
l = []
cl = []
for i, _ in enumerate(range(d)):
    p, c = map(int, input().split())
    l.append([p, c])
    cl.append(p * 100 * (i + 1) + c)

ans = float("INF")
for flags in itertools.product([0, 1], repeat=d):
    q = []
    cost = g
    cnt = 0
    for i, flag in enumerate(flags):
        if flag:
            cost -= cl[i]
            cnt += l[i][0]
        else:
            q.append(i)

    q.reverse()
    if cost > 0:
        for i in q:
            if math.ceil(cost / (100 * (i + 1))) <= l[i][0]:
                cnt += math.ceil(cost / (100 * (i + 1)))
                break
        else:
            cnt = float("INF")
    ans = min(ans, cnt)
print(ans)


Measured memory_bytes: 3064
N, M = map(int,input().split())
S = [list(map(int,input().split())) for _ in range(N)]
P = [list(map(int,input().split())) for _ in range(M)]

result = []
for s in S:
  a = s[0]
  b = s[1]
  for p in P:
    c = p[0]
    d = p[1]
    direct = abs(a-c)+abs(b-d)
    result.append(direct)
  point = min(result)
  print(result.index(point) + 1)
  result = []

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

using namespace std;

#define INF 2000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;


int main()
{
	string s;
	cin >> s;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '9') {
			s[i] = '1';
		} else if (s[i] == '1') {
			s[i] = '9';
		}
	}
	cout << s << "\n";

}


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

using namespace std;

const long long INF = 1000000000000000000;

void Main() {
    long long V, E, r;
    cin >> V >> E >> r;
    typedef pair<long long, long long> Weight_To;
    vector<set<Weight_To> > graph(V, set<Weight_To>());
    for (long long i = 0; i < E; ++i) {
        long long s, t, d;
        cin >> s >> t >> d;
        graph[s].insert(make_pair(d, t));
    }

    // Dijkstra
    vector<long long> d(V, INF);
    d[r] = 0;
    typedef pair<long long, long long> TotalCost_Current;
    priority_queue<TotalCost_Current, vector<TotalCost_Current>, greater<TotalCost_Current> > q;
    q.push(make_pair(0, r));
    while (!q.empty()) {
        TotalCost_Current tc_curr = q.top();
        long long costSoFar = tc_curr.first;
        long long curr = tc_curr.second;
        q.pop();
        if (d[curr] < costSoFar) {
            continue;
        }
        set<Weight_To> nextNodes = graph[curr];
        for (auto e : nextNodes) {
            if (d[e.second] > d[curr] + e.first) {
                d[e.second] = d[curr] + e.first;
                q.push(make_pair(d[e.second], e.second));
            }
        }
    }

    for (long long i = 0; i < V; ++i) {
        if (d[i] == INF) {
            cout << "INF" << endl;
        }
        else {
            cout << d[i] << endl;
        }
    }
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}



Measured memory_bytes: 40768
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

zx = list(range(max(x)+1,101))
zy = list(range(-100, min(y)+1))
kanou = set(zx) & set(zy)
if len(kanou) == 0:
    print('War')
else:
    for i in kanou:
        if X < i <= Y:
            print('No War')
            break
    else:
        print('War')

Measured memory_bytes: 3064
//2015
#include<iostream>
using namespace std;
int main(void){
	int i,n,m,a[1000],k=1,work=0;
	cin>>n>>m;
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	for(k=1;k<=m;k++){
		for(i=0;i<n-1;i++){
			if(a[i]%k>a[i+1]%k){
				work=a[i];
				a[i]=a[i+1];
				a[i+1]=work;
			}	
		}
	}
	for(i=0;i<n;i++){
		cout<<a[i]<<endl;
	}
	return 0;
}//0:30:24.01 GameOver.


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL << 30)
#define LLINF (1LL << 60)
#define PI 3.14159265359
#define EPS 1e-12
#define int ll

int prime[1000000];
signed main(void) {
  REP(i, 1000000) prime[i] = 1;
  prime[0] = prime[1] = 0;
  for (int i = 2; i * i <= 1000000; i++) {
  	if (prime[i]) {
  		for (int j = 2 * i; j <= 1000000; j += i) {
  			prime[j] = 0;
  		}
  	}
  }
  //REP(i, 10) cout << prime[i] << " "; cout << endl;
  FOR(i, 1, 1000000) {
    prime[i] += prime[i-1];
    //cout << prime[i] << endl;
  }
  int n;
  while (cin >> n) {
    cout << prime[n] << endl;
  }
  return 0;
}

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

#define pb push_back
#define ff first
#define ss second

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

const int MAXN = 100 + 17;

int n, a[MAXN];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		if (a[i] % 3 != 0 && a[i] % 5 != 0 && a[i] % 2 == 0)
			return cout << "DENIED" << endl, 0;
	cout << "APPROVED" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<unistd.h>
#include <array>
#include <map> 




using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd(int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}

int moji(char in)
{
    int ans = (int)in-(int)'a';
    if((ans < 0) || (ans > 25)){
        ans = 26;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}

int binary_searchh(long long x,long long k[],int n){
  int l=0;
  int r=n;
  while(r-l>=1){
    int i=(l+r)/2;
    if(k[i]==x)return i;
    else if(k[i]<x)l=i+1;
    else r=i;
  }
  return -1;
}

struct File {
    int aa;
    int bb;

    File(const int& aa, const int& bb)
        : aa(aa), bb(bb) {}
};

bool operator<(const File& a, const File& b)
{
    // ファイル種別、ファイル名の順番で優先順位を付けて比較
    return std::tie(a.aa, a.bb) < std::tie(b.aa, b.bb);
}




int main(){
  float T,X;
  cin>>T>>X;
  cout<<T/X<<endl;








  


}


  
  



Measured memory_bytes: 256
#include<iostream>

int fun(int n)
{
    return n*(n-1)/2;
}

int main()
{
    int m,n;
    long long he=0;
    scanf("%d %d",&m,&n);
    if(m>1)
    {
        he=fun(m);
    }
    if(n>1)
    {
        he+=fun(n);
    }
    printf("%lld\n",he);
    
    return 0;
}



Measured memory_bytes: 256
import sys
input = sys.stdin.readline

S = list(input().strip())

c = [0] * 4
t = "B"
for i in range(len(S)):
    if S[i] != t:
        t = S[i]
        c[0] += 1
        
t = "B"
for i in reversed(range(len(S))):
    if S[i] != t:
        t = S[i]
        c[1] += 1

t = "W"
for i in range(len(S)):
    if S[i] != t:
        t = S[i]
        c[2] += 1
        
t = "W"
for i in reversed(range(len(S))):
    if S[i] != t:
        t = S[i]
        c[3] += 1
            
print(min(c))


Measured memory_bytes: 3956
#include<iostream>
#include <cmath>
#include<vector>
#define rep(i, n) for (int i=0;i<n;i++)
#include <map> 
#include<algorithm>
#include <numeric>
#include<deque>
#include<queue>
#include<string>
#include <iomanip>

using namespace std;
typedef long long ll;

int main(void){
    int n;
    cin>>n;
    double ans=0;
    if(n%2==0){
        ans=0.5;
    }
    else{
        ans=n/2+1;
        ans/=n;
    }
    cout<<setprecision(12)<<ans<<endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

typedef pair<int, int> Point;
struct edge { int to, cost; };

const int MAX_V = 500;
const int INF = 100000000;

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

int dijkstra(int s, int t){
  priority_queue<Point, vector<Point>, greater<Point> > que;
  fill(d, d + V, INF);
  d[s] = 0;
  que.push(Point(0, s));
  while(!que.empty()){
    Point p = que.top(); que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    for(int i=0;i<G[v].size();i++){
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost){
        d[e.to] = d[v] + e.cost;
        que.push(Point(d[e.to], e.to));
      }
    }
  }
  return d[t];
}

void init(){
  for(int i=0;i<MAX_V;i++){
    G[i].clear();
  }
}

main(){
  int n, m;
  while(cin >> n >> m && (n | m)){
    init();
    string s, p, g;
    map<string, int> stoi;
    map<int, string> itos;
    cin >> s >> p >> g;
    int cnt = 0;
    for(int i=0;i<m;i++){
      string a, b;
      int d, t;
      cin >> a >> b >> d >> t;
      if(stoi.find(a) == stoi.end()){
        stoi[a] = cnt;
        itos[cnt++] = a;
      }
      if(stoi.find(b) == stoi.end()){
        stoi[b] = cnt;
        itos[cnt++] = b;
      }
      G[stoi[a]].push_back((edge){stoi[b], d/40 + t});
      G[stoi[b]].push_back((edge){stoi[a], d/40 + t});
    }
    V = n;
    cout << dijkstra(stoi[s], stoi[p]) + dijkstra(stoi[p], stoi[g]) << endl;
  }
  return 0;
}

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

int main() {
    int a,b;
    string s;
    while (true) {
        cin >> a >> s >> b;
        if (s == "+") {
            cout << a+b <<endl;
        }else if (s== "-"){
            cout << a-b <<endl;
        }else if (s=="*"){
            cout << a*b <<endl;
        }else if (s=="/"){
            cout << a/b <<endl;
        }else{
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 3124
#include <iostream>
#include <stdlib.h>
using namespace std;
int GCD(int,int);
int main() {
	int N,X,x[100010];
        cin>>N>>X;
	for(int i=0;i<N;i++){
	    cin>>x[i];
	    x[i]=abs(x[i]-X);
	}
	for(int i=0;i<N-1;i++) x[i+1]=GCD(x[i],x[i+1]);
	cout<<x[N-1]<<endl;
}
int GCD(int a,int b){
    int hoge;
    do{
        hoge=a%b;
        a=b;
        b=hoge;
    }while(hoge!=0);
    return a;
}


Measured memory_bytes: 640
#include<cstdio>
const int N=(int)2e1+5;
int a[N],b[N],c[N],d[N];
int main(int argc,char**argv){
  register int n;scanf("%d",&n);
  for(register int i=1;i<=n;++i)
    scanf("%d",a+i);
  for(register int i=1;i<=n;++i)
    scanf("%d",b+i);
  for(register int i=1;i<n;++i)
    scanf("%d",c+i);
  register int lst=-1,ans=0;
  for(register int i=1;i<=n;++i){
    register int x=a[i];
    if(x==lst+1)ans+=c[lst];
    ans+=b[x];lst=x;
  }
  printf("%d\n",ans);
}

Measured memory_bytes: 128
import java.util.*;
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();//ボード数
		String sample = s.next();//s.next();//元となる文字
		char[] samples = new char[sample.length()];//sample.length()];//[sample.length()];
		for(int i=0; i<samples.length; i++){
			samples[i] = sample.charAt(i);
			//System.out.println(samples[i]);
		}
		String[] board = new String[N];
		int count=0;
		int muri = 2;
		/*int iend = 0;
		int jend = 0;
		int kend = 0;*/
		int result = 0;
		do{
			board[0] = s.next();
			N--;
		end: for(int i=0; i<board[0].length(); i++){
			if(samples[0]!=board[0].charAt(i)) continue;
			//System.out.println("i="+i);
			//iend=i;
			for(int j=i; j<board[0].length(); j++){
				if(samples[1]!=board[0].charAt(j)) continue;
				//System.out.println("j="+j);
				count = j-i;
				int flag = 2;
				//jend = j;
				muri = 2;
				a:for(int k=j+count; k<board[0].length();k+=count){
					if(samples[muri]!=board[0].charAt(k)){
						//k+=count;
						break a;
					}
					//System.out.println("k="+k);
					muri++;
					flag++;
					//kend = k;
					if(flag==sample.length()){
						result++;
						break end;
					}
				}
			}
		}
		}while(N>0);
		//System.out.println(iend+" "+jend+" "+kend);
		System.out.println(result);
	}
}

Measured memory_bytes: 20684
#include<stdio.h>
int fib(int N) {
    int ans[100], i;
    ans[0] = ans[1] = 1;
    for ( i = 2; i <= 44; i++ ) ans[i] = ans[i - 1] + ans[i - 2];
    return ans[N];
}
int main(void){
    int n;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    return 0;
}

Measured memory_bytes: 1820
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int h,w,n;
    cin>>h>>w>>n;
    int ans=0;
    int mx;
    if(h<w)
    {
        mx=w;
    }
    else 
        mx=h;
    ans=n/mx;
    if(n%mx!=0)
        ans++;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

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

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, N);
    IN(ll, K);
    vi d(K);
    vvi A(K);
    REP(i, K)
    {
        cin >> d[i];
        A[i] = vi(d[i]);
        REP(j, d[i])
        {
            cin >> A[i][j];
        }
    }
    vector<bool> b(N + 1, false);
    REP(i, K)
    {
        REP(j, d[i])
        {
            b[A[i][j]] = true;
        }
    }
    ll ans = N;
    REP1(i, N)
    {
        ans -= b[i];
    }
    OUT(ans);
}

Measured memory_bytes: 3660
import math

def isprime(n):
    for k in range(2,math.floor(math.sqrt(n))+1):
        if n%k == 0:
            return False
    return True

N = int(input())
if N == 1:
    print(0)
    exit(0)

P = [N]
for k in range(2,math.floor(math.sqrt(N))+1):
    if N % k == 0:
        P.append(k)
        P.append(N//k)
P = sorted(P)
Q = []
for k in range(len(P)):
    if isprime(P[k]) == True:
        temp = 0
        while N%P[k] == 0:
            N //= P[k]
            temp += 1
        Q.append(temp)

ans = 0
for e in Q:
    if e > 0:
        t = 0
        for k in range(1,100):
            t += k
            if t <= e:
                ans += 1
            else:
                break
print(ans)


Measured memory_bytes: 9276
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b); (i) >= (a); --(i)) //Reversi for
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;

int asc(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int desc(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int main()
{
    int n,k,ans = 1;
    cin >> n >> k;
    rep(i, n){
        if (ans * 2 <  ans + k) {
            ans = ans * 2;
        }else{
            ans += k;
        }
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int main(){
    int n,t;
    cin>>n>>t;
    vector<pair<int,int>>vp;
    for(int i=0;i<n;i++)
    {
        int f,s;
        cin>>f>>s;
        vp.push_back({f,s});
    }
    int cost=-1;
    for(int i=0;i<vp.size();i++)
    {
        if(t>=vp[i].second){
            if(cost==-1||cost>vp[i].first){
                cost=vp[i].first;
            }
        }
    }
    if(cost==-1)cout<<"TLE";
    else
    cout<<cost;
}

Measured memory_bytes: 3580
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
#from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
B = LI()
A = []
A.append(B[0])
for i in range(1, n-1):
    A.append(min(B[i-1], B[i]))
A.append(B[n-2])
print(sum(A))


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

int dp[100];

//最大公約数
int gcd(int x, int y){
  if(x % y == 0) return 1;
  return gcd(y, x % y);
}
//最小公倍数
int lcm(int x, int y){
  return x * y / gcd(x, y);
}
//フィボナッチ数列
//配列dpを-1で初期化する
int fib(int n){
  if(n == 0 || n == 1) return dp[n] = 1;
  if(dp[n] != -1) return dp[n];
  return dp[n] = fib(n - 1) + fib(n - 2);
}
//階乗計算(factorial)
int fact(int n){
  if(n = 1) return 1;
  return n * fact(n - 1);
}
//累乗計算(Exponentiation)
//x**y
ll expo(int x, int y){
  ll ans = 1;
  rep(i, y){
    ans *= x;
  }
  return ans;
}
//桁数
int keta(ll x){
  if(x == 0) return 1;
  int res = 0;
  while(x){
    x /= 10;
    res++;
  }
  return res;
}


int main(){
  char a[4];
  rep(i, 4) cin >> a[i];

  if(a[0] == a[1] && a[2] == a[3] && a[0] != a[2]) cout << "Yes" << endl;
  else if(a[0] == a[2] && a[1] == a[3] && a[0] != a[1]) cout << "Yes" << endl;
  else if(a[0] == a[3] && a[2] == a[1] && a[0] != a[2]) cout << "Yes" << endl;
  else cout << "No" << endl;
}


/*





















*/



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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,m;
int a[125252];
ll imo[252521];
ll imo2[252521];

int main(){
  scanf("%d%d",&n,&m);
  REP(i,n)scanf("%d",a+i),a[i]--;
  REP(i,n-1){
    int from = a[i];
    int to = a[i+1];
    if(to < from)to += m;
    imo[from+1]++;
    imo[to+1]--;
    imo2[to+1]-=(to-from);
  }
  REP(i,2*m+1)imo[i+1]+=imo[i];
  REP(i,2*m+1)imo2[i]+=imo[i];
  REP(i,2*m+1)imo2[i+1]+=imo2[i];
  REP(i,m)imo2[i]+=imo2[i+m];
  int x = max_element(imo2,imo2+m)-imo2;
  ll ans = 0;
  REP(i,n-1){
    int from = a[i];
    int to = a[i+1];
    if(to < from)to += m;
    int y = x;
    if(y < from)y += m;
    if(from < y && y <= to){
      ans++;
      from = y;
    }
    ans += to-from;
  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 4224
n = int(input())
p = []
for i in range(n):
    num = int(input())
    num -= 1
    p.append(num)

cnt = [0] * n

for i in range(n):
    if p[i] == 0:
        cnt[0] = 1
    else:
        cnt[p[i]] = cnt[p[i] - 1] + 1

max_p = max(cnt)

print(n - max_p)

Measured memory_bytes: 84932
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) memset(arg,n,sizeof(arg))
using std::cin;
typedef long long ll;
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
const int INF=1e+9;
const ll INFLL=1e+17;
int T;
ll A[310],B[310],C[310],D[310];
ll gcd(ll a,ll b){
  if(b==0) return a;
  else return gcd(b,a%b);
}
void solve(int i){
  ll a=A[i],b=B[i],c=C[i],d=D[i];
  if(a<b){
    prin("No");return ;
  }
  if(d<b){
    prin("No");return ;
  }
  a%=b;
  ll g=gcd(b,d);
  //  prin(g);
  if((b-a)%g==0){
    if(b-g>c){
      prin("No");return ;
    }
    else{
      prin("Yes");return ;
    }
  }
  else{
    ll x=(b-a)/g*g+a;
    if(x>c){
      prin("No");return ;
    }
    else{
      prin("Yes");return ;
    }
  }
}
int main(){
  cin>>T;
  rep(i,T) cin>>A[i]>>B[i]>>C[i]>>D[i];
  rep(i,T){
    solve(i);
  }
  return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& e : a) cin >> e;

  int r = 0;
  for (auto e : a) {
    if (e == r + 1) r++;
  }
  cout << (r == 0 ? -1 : n - r) << endl;
}


Measured memory_bytes: 1024
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_B


class Node:
    def __init__(self,
                 parent,
                 left,
                 right):
        self.parent = parent
        self.left = left  # 左の子ノード
        self.right = right  # 右の**子**


def get_all_height(T: dict, H: dict, u: int):
    '''
    深さ優先探索で各地点をめぐりながらHに高さ情報セットしていく
    '''
    h_left, h_right = 0, 0  # Noneによって代入されなかったとき用
    # 本では右から左の方に探索していったけど
    # キモいのでここでは左から右に探索していくことにする
    if T[u].left is not None:
        h_left = get_all_height(T, H, T[u].left) + 1
    if T[u].right is not None:
        h_right = get_all_height(T, H, T[u].right) + 1
    ret = max(h_left, h_right)
    H[u] = ret
    return ret


def get_all_depth(T, D: dict, u, p: int):
    '''
    まあHがわかってればdepthに変換可能なんだけど練習のために再帰関数で実装する。

    Dは深さを格納するための辞書
    pは現在の深さ
    '''
    D[u] = p
    if T[u].left is not None:
        get_all_depth(T, D, T[u].left, p+1)
    if T[u].right is not None:
        get_all_depth(T, D, T[u].right, p+1)


def ret_sibling(T, u):
    '''
    一度親を経由すれば良い
    '''
    parent = T[u].parent
    if parent is None:
        return -1  # 根は
    ret = T[parent].left if T[parent].left != u else T[parent].right
    if ret is None:
        return -1
    return ret


def ret_degree(T, u):
    ret = 2
    if T[u].left is None:
        ret -= 1
    if T[u].right is None:
        ret -= 1
    return ret


# データを読み込む
n = int(input())
T = {key: Node(None, None, None) for key in range(n)}  # 初期化
for _ in range(n):
    tmp = list(map(int, input().split()))
    # 左から処理
    if tmp[1] != -1:
        T[tmp[0]].left = tmp[1]  # 子の代入
        T[tmp[1]].parent = tmp[0]  # 親の代入
    if tmp[2] != -1:
        T[tmp[0]].right = tmp[2]  # 子の代入
        T[tmp[2]].parent = tmp[0]  # 親の代入

# 根の探索
for k, v in T.items():
    if v.parent is None:
        ROOT = k
        break
else:
    raise ValueError("ROOTが存在しないなんておかしい")

# 深さと高さの探索
D = {}
get_all_depth(T, D, ROOT, 0)
H = {}
get_all_height(T, H, ROOT)


def print_for_a_node(u):
    if T[u].parent is None:
        parent = -1
    else:
        parent = T[u].parent

    sib = ret_sibling(T, u)
    deg = ret_degree(T, u)
    node_type = 'internal node' if deg != 0 else 'leaf'
    if parent == -1:
        node_type = 'root'

    print(
        f'node {u}: parent = {parent}, sibling = {sib}, degree = {deg}, depth = {D[u]}, height = {H[u]}, {node_type}')


for node in range(n):
    print_for_a_node(node)



Measured memory_bytes: 5680
#include <bits/stdc++.h>
using namespace std;
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
const ull BASE = 1e9 + 7;


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (true) {
        int n, m;
        cin >> n >> m;
        if (n == 0) break;
        vector<vector<int>> g(n);
        rep(i, m) {
            int a, b;
            cin >> a >> b;
            a--; b--;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        bool visited[n] = {};
        int dist[n];
        fill(dist, dist + n, 1e9);
        queue<int> q;
        q.push(0);
        visited[0] = true;
        dist[0] = 0;
        while (!q.empty()) {
            int now = q.front(); q.pop();
            for (auto to : g[now]) {
                if (visited[to]) continue;
                q.push(to);
                visited[to] = true;
                dist[to] = dist[now] + 1;
            }
        }
        int ans = 0;
        rep2(i, 1, n) if (dist[i] <= 2) ans++;
        cout << ans << endl;
    }
}

Measured memory_bytes: 3244
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vd=vector<double>;
using vvd=vector<vd>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using vs=vector<string>;
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define LINF    	((ll)1ll<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.141592653589793

template<class S,class T>ostream& operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	int n;
	cin>>n;
	cout<<((n+1)/2) * (n/2)<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while ((line = br.readLine()) != null && !line.isEmpty()) {
			int n = Integer.parseInt(line);
			if (n == 0) {
				break;
			}

			int[] wait = new int[n];
			long sum = 0;
			for (int i = 0; i < n; i++) {
				wait[i] = Integer.parseInt(br.readLine());
			}
			Arrays.sort(wait);
			for (int i = 0, j = n - 1; i < n - 1; i++, j--) {
				sum += wait[i] * j;
			}
			System.out.println(sum);
		}
	}
}

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

const ll INF = 1e18;
const ll MOD = 1000000007;
const ll MX = 0; //最大値

#define rep(i,n) for(ll i=0; i<(ll)(n); i++)
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define PB push_back
#define F first
#define S second

int main(){
    ll n, d; cin >> n >> d;
    vector<ll> x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];
    
    d *= d;
    ll cnt = 0;
    rep(i, n){
        if (d >= x[i]*x[i] + y[i]*y[i]) cnt++;
    }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 6428
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using VI=vector<ll>;
using VD=vector<ld>;
using VVI=vector<VI>;
using VC=vector<char>;
using VVC=vector<VC>;
using VS=vector<string>;
using PLL =pair<ll,ll>;
using PLD=pair<ld,ld>;
using VPLL=vector<PLL>;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element((x).begin(),(x).end())
#define MIN(x) *min_element((x).begin(),(x).end())
#define SORTR(x) sort((x).rbegin(),(x).rend())
#define SORT(x) sort((x).begin(),(x).end())
#define SUM(x) accumulate((x).begin(),(x).end(), 0)
#define FILL(x,a) fill(x.begin(),x.end(),a)
#define EACH(i,x) for(typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define COUT(x) cout<<x<<"\n"

const ll INF = 1e18;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;
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; }
template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last){reverse(middle, last); return next_permutation(first , last);}
ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll GCD(VI v){ll a = v[0]; for (ll i = 1; i<SIZE(v); i++) {a = gcd(a, v[i]);} return a;}
ll LCM(VI v){ll a = v[0]; for (ll i = 1; i<SIZE(v); i++) {a = lcm(a, v[i]);} return a;}

void Main()
{
	ll res=-1;
	ll n,m,x;
	VI c(12,0);
	VVI a(12,VI(12,0));

	cin >>n>>m>>x;
	//VVI ca(n,VI(m+1,0));
	//REP(i,n) {
	//	REP(j, m+1) {
	//		cin >> ca[j][i];
	//	}
	//}
	//SORT(ca);
	//do{
	//}//while (next_permutation(ALL(ca));
	REP(j,n){
		cin>>c[j];
		REP(i,m){
			cin>>a[j][i];
		}
	}
	VI b(12,x);

	for (ll i0 = 0; i0<=1; ++i0) {
	for (ll i1 = 0; i1<=1; ++i1) {
	for (ll i2 = 0; i2<=1; ++i2) {
	for (ll i3 = 0; i3<=1; ++i3) {
	for (ll i4 = 0; i4<=1; ++i4) {
	for (ll i5 = 0; i5<=1; ++i5) {
	for (ll i6 = 0; i6<=1; ++i6) {
	for (ll i7 = 0; i7<=1; ++i7) {
	for (ll i8 = 0; i8<=1; ++i8) {
	for (ll i9 = 0; i9<=1; ++i9) {
	for (ll i10 = 0; i10<=1; ++i10) {
	for (ll i11 = 0; i11<=1; ++i11) {
		VI tmp(m,0);
		VI arr = { i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11 };
		ll cost=0;
		REP(j, 12) {
			if (arr[j]==1) {
				cost+=c[j];
				REP(i,m) {
					tmp[i] +=a[j][i];
				}
			}
		}
		if(MIN(tmp)>=x){
			ll curr=INF;
			if(res!=-1)
				curr=res;
			if(chmin(curr,cost)){
				res=cost;
			}
		}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	}
	COUT(res);
	return;
}

int main()
{
	std::cin.tie(0);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


Measured memory_bytes: 3664
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m=[input()for _ in range(h)]
d=[[I]*w for _ in range(h)]
q=deque([(s-1,t-1,1)])
while q:
  y,x,c=q.popleft()
  if d[y][x]<I:continue
  d[y][x]=c
  for i,j in(y-1,x),(y,x-1),(y,x+1),(y+1,x):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.appendleft((i,j,c))
  for i,j in(y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),(y-1,x-2),(y-1,x-1),(y-1,x+1),(y-1,x+2),(y,x-2),(y,x+2),(y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),(y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

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

int main()
{
  double x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  double diff_x = x2 - x1, diff_y = y2 - y1;
  double dist = sqrt(pow(diff_x, 2) + pow(diff_y, 2));
  printf("%.8f\n", dist);
}


Measured memory_bytes: 3204
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://agc004.contest.atcoder.jp/tasks/agc004_b>
問題文============================================================
 高橋君は異世界に住んでいます。 この世界には N 色のスライムがいます。
 最初、高橋君はどの色のスライムも飼っていません。 高橋君の目標は、全色のスライムを一緒に飼うことです。
 
 高橋君は次の 2 種類の操作を行えます。
 
 今飼っていないスライムの色 i (1≤i≤N) をひとつ選ぶ。 色 i のスライムを捕まえて飼う。この操作には ai 秒掛かる。
 
 魔法を唱える。 すると、今飼っている各スライムについて、色 i (1≤i≤N−1) のスライムは色 i+1 へ変色する。
 ただし、色 N のスライムは色 1 へ変色する。 この操作には x 秒掛かる。
 
 高橋君が全色のスライムを一緒に飼うためには、最短で合計何秒掛かるかを求めてください。
=================================================================

解説=============================================================

 全体でどこのスライムを捕獲して何回変色させるのが最適かどうかといった事ではなく
 k(0 <= k <= N-1)回変色させる事を前提とした時、あるスライムiはどこで捕まえるのが最適かといった事を考える
 
 全体で k 回変色させることをあらかじめ決めうちしておくと
 
 あるスライム i は
 
 スライムi-kを捕まえて k回変色
 1回変色させたのち、 スライムi-k+1を捕まえて k-1回変色
 .
 .
 .
 j回変色させたのち、 スライムi-k+jを捕まえて k-j回変色
 
 といった考えができるので、i-k ... i までのどのスライムを捕まえても良くなる
 
 よって,
 
 k回変色させると決めた時
 あるスライムiについて捕まえるスライム min{ ai,ai-1,ai-2,...ai-k}
 を b とすると
 k*x + Σb
 が全スライムを揃えるのに最小なコストとなる
 
 ここで、 k を k + 1 にするとき b のテーブルを使い回せば 各スライムについて b はO(1)でもとまるので
 O(N^2)の計算量となり間に合う
 
================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N,x; cin >> N >> x;
    vector<ll> a(N);
    for(auto &in:a) cin >> in;
    vector<ll> b(N,LINF);
    ll ans = LINF;
    // i * x + Σb[j]_i
    for(int i = 0; i < N;i++){
        ll tmp = 0;
        for(int j = 0; j < N;j++){
            b[j] = min(b[j],a[(j-i+N)%N]);
            tmp += b[j];
        }
        ans = min(ans,i*x+tmp);
    }
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using static System.Math;
using Debug = System.Diagnostics.Debug;

static class P
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var res = new int[n];
        for (int i = a.Length; i >= 1; i--)
        {
            int sum = 0;
            for (int j = i; j <= n; j += i)
            {
                sum += res[j - 1];
            }
            res[i - 1] = sum % 2 != a[i - 1] ? 1 : 0;
        }
        var balls = res.Select((elem, count) => new { elem, count }).Where(x => x.elem == 1).Select(x => x.count + 1).ToArray();
        Console.WriteLine(balls.Length);
        if (balls.Length != 0) Console.WriteLine(string.Join("\n", balls));
    }
}


Measured memory_bytes: 35540
N = int(input())
W = list(map(int, input().split(" ")))
X, Y = 0, sum(W)
min_diff = abs(Y - X)
for i in range(0, N):
    X += W[i]
    Y -= W[i]
    tmp = abs(X - Y)
    if tmp < min_diff:
        min_diff =tmp
print(min_diff)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using i64 = int64_t;
using f80 = __float80;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
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;}
template<typename T> ostream &operator<<(ostream &os, const vector< T > &v){
  rep(i,v.size()) os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template<typename T> istream &operator>>(istream &is, vector< T > &v){
  for(T &in : v) is >> in;
  return is;
}

void Main()
{
  i64 N, K;
  cin >> N >> K;
  vi A(N+1);
  rep(i,N){
    cin >> A[i+1];
  }

  int c = 1;
  while(K) {
    if(K&1) c = A.at(c);
    vi NA(N+1);
    rep(i,N+1){
      NA[i] = A[A[i]];
    }
    A.swap(NA);
    K>>=1;
  }

  cout << c << "\n";
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}

Measured memory_bytes: 6344
// #include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <math.h>
#include <algorithm> // std::sort, std::min, std::next_permutation, std::lower_bound
#include <iomanip> // std::setprecision
#include <cmath> // std::ceil
#include <numeric> // std::gcd, std::lcm
#include <limits> // std::numeric_limits<long int>::max()
#include <unordered_map>
#include <map>
#include <cmath> // std::atan2
#include <deque>
#include <queue>

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

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

  vector<ll> ans(N+1,0);
  
  for (ll x=1; x<=100; ++x) {
    for (ll y=1; y<=100; ++y) {
      for (ll z=1; z<=100; ++z) {
        ll val = x*x + y*y + z*z + x*y + y*z + z*x;
        if (val <= N) {
          ans[val]++;
        }
      }
    }
  }
  for (ll i=1; i<=N; ++i) {
    cout << ans[i] << endl;
  }
  return 0;
}



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


int main() {
	 long int Y = 0;
	long int N;
	cin >> N;
	 int A[100000];
	for (int i = 0; i < N; i++) {
			cin >> A[i];
		}
	sort(A, A+N);
	 long int W = A[0];
	 long int R = 0;
	for (int i = 0; i < N; i++) {
		
		if (A[i] == W) {
			R++;

		}
		else {
			W = A[i];

			if (A[i-1] == R) {

			}
			else if(A[i-1]>R){
				Y += R;
			}
			else {
				Y += (R-A[i-1]);
			}
			if(i!=N-1)R = 1;
		}
		
		
		
	}

	if (A[N - 1] == R) {

	}
	else if (A[N- 1]>R) {
		Y += R;
	}
	else {
		Y += (R - A[N - 1]);
	}


	cout << Y << endl;

	return 0;
}



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

using namespace std;

int main()
{
   int n;
   cin >> n;
   int *v=new int[n];
   for(int i=0;i<n;i++){cin >> v[i];}
   int *num_cnt1=new int[100001];
   int *num_cnt2=new int[100001];
   for(int i=0;i<100001;i++){num_cnt1[i]=0;num_cnt2[i]=0;}
   int temp=0;
   int max1=0;
   int max1v=0;
   int sec1=0;
   int sec1v=0;
   int max2=0;
   int max2v=0;
   int sec2=0;
   int sec2v=0;
   
   
   
  for(int i=0;i<n;i=i+2)
  {
      num_cnt1[v[i]]+=1;
      if(v[i]>temp){temp=v[i];}
  }
  for(int i=1;i<=temp;i++)
  {
      
      if(max1<num_cnt1[i]){sec1=max1;max1=num_cnt1[i];sec1v=max1v;max1v=i;}else if(sec1<num_cnt1[i]){sec1=num_cnt1[i];sec1v=i;}
      
  }
   temp=0;
   
  for(int i=1;i<n;i=i+2)
  {
      num_cnt2[v[i]]+=1;
      if(v[i]>temp){temp=v[i];}
  }
  for(int i=1;i<=temp;i++)
  {
      if(max2<num_cnt2[i]){sec2=max2;max2=num_cnt2[i];sec2v=max2v;max2v=i;}else if(sec2<num_cnt2[i]){sec2=num_cnt2[i];sec2v=i;}
  } 
  
   if(max1v!=max2v)
   {
      cout << n-max1-max2 <<endl;  
   }else{
      cout << min(n-max1-sec2,n-sec1-max2) << endl;
       
   }
   
   
   delete[] v;
   delete[] num_cnt1;
   delete[] num_cnt2;
   return 0;
}

Measured memory_bytes: 1408