akhauriyash/Code-Regression huggingface dataset:
//
// Created by kuroneko on 2019-09-28.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

#define INF 1000000000000009LL
#define MOD 1000000007LL

typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight):src(src), dst(dst), weight(weight) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

int dp[(1<<12) + 5][1000+5];

int main() {
    int N, M; cin >> N >> M;
    vector<int> a(M), b(M);
    vector<vector<int>> c(M);

    for (int i = 0; i < (1<<N); i++) {
        for (int j = 0; j <= M; j++) {
            if (i == 0) dp[i][j] = 0;
            else dp[i][j] = 1000000000;

        }
    }

    dp[0][0] = 0;


    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i];
        for (int j = 0; j < b[i]; j++) {
            int cc; cin >> cc;
            c[i].emplace_back(cc-1);
        }
    }

    for (int i = 1; i <= M; i++) {
        int now = 0;
        for (int k = 0; k < c[i-1].size(); k++) {
            now |= (1<<c[i-1][k]);
        }
        for (int bit = 0; bit < (1<<N); bit++) {
            int tmp = bit & ~now;
            dp[bit][i] = min(dp[bit][i-1], dp[tmp][i-1]+a[i-1]);
        }
    }

    if (dp[(1<<N)-1][M] == 1000000000) cout << "-1" << endl;
    else cout << dp[(1<<N)-1][M] << endl;
    return 0;
}


Measured memory_bytes: 16384
#include<iostream>
#include<iomanip>
#include<cstdio>

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>
#include<numeric>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
template <class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template <class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
const ll INF = 1e18+1;


int main() {
  
    double a, b, x;
    cin >> a >> b >> x;
    
    if (x <= a * a * b / 2.0) {
    double c = atan(a * b * b/2.0/x) * 180 / M_PI;
    printf("%.9lf", c);
    } else {
        double c = atan((a * a * b - x) *2/a/a/a) * 180 / M_PI;
        printf("%.9lf", c);
    }


    
}

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

arr = [list(map(int,input().split())) for _ in range(N)]
dp = [ list([0,0,0]) for i in range(N)]
for i,l in enumerate(arr):
  if i == 0:
    dp[0] = l
    continue
  dp[i] = [max(dp[i-1][1:])+l[0], max(dp[i-1][0],dp[i-1][2])+l[1],max(dp[i-1][:2])+l[2]]
print(max(dp[-1]))
#print(dp)

    

Measured memory_bytes: 53492
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 200010
using namespace std;

int n,m;
pair<int,int> a[MAXN];
priority_queue<int> S1,S2;

int main(){
#ifdef DEBUG
	freopen("F.in","r",stdin);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].first,&a[i].second);
		a[i].second=-a[i].second;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) a[i].second=-a[i].second;
	int now=1;
	int ans=0;
	while(now<=n && a[now].first==0)
		S2.push(-a[now++].second);
	for(int i=1;i<=m;i++){
		if(now<=n){
			ans++;
			S1.push(-a[now++].second);
			while(now<=n && a[now].first==i){
				if(a[now].second>-S1.top()){
					S2.push(S1.top());
					S1.pop();
					S1.push(-a[now].second);
				}else S2.push(-a[now].second);
				now++;
			}
		}else{
			if(!S2.empty() && -S2.top()<=i){
				S2.pop();
				ans++;
			}
		}
	}
	printf("%d\n",n-ans);
	return 0;
}


Measured memory_bytes: 3320
loop do
    input = gets.split(" ").map do |i| i.to_i end
    if input[0] == -1 && input[1] == -1 && input[2] == -1
        break
    elsif input[0] == -1 || input[1] == -1
        puts "F"
    elsif input[0] + input[1] >= 80
        puts "A"
    elsif input[0] + input[1] >= 65 && input[0] + input[1] < 80
        puts "B"
    elsif input[0] + input[1] >= 50 && input[0] + input[1] < 65
        puts "C"
    elsif input[0] + input[1] >= 30 && input[0] + input[1] < 50 && input[2] >= 50
        puts "C"
    elsif input[0] + input[1] >= 30 && input[0] + input[1] < 50
        puts "D"
    else
        puts "F"
    end
end

Measured memory_bytes: 8712
from collections import deque

dq = deque()
n = int(input())
for _ in range(n):
    cmd = input().split()
    if cmd[0] == "insert":
        dq.appendleft(cmd[1])
    elif cmd[0] == "delete":
        try:
            dq.remove(cmd[1])
        except ValueError:
            pass
    elif cmd[0] == "deleteFirst":
        dq.popleft()
    else:
        dq.pop()
print(*dq)

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

#define int long long

int32_t main(){
    int N,W;
    cin>>N>>W;
    int weights[N], values[N];
    for(int ind=0; ind<N; ind++){
        cin>> weights[ind];
        cin>> values[ind];
    }
    int dp[N+1][W+1];
    for(int items=0; items<=N; items++){
        for(int weight=0; weight<=W; weight++){
            if(items==0 || weight==0) dp[items][weight]=0;
            else if(weight-weights[items-1] >=0)
                dp[items][weight]=max(dp[items-1][weight], values[items-1]+dp[items-1][weight-weights[items-1]]);
            else dp[items][weight] = dp[items-1][weight];
        }
    }
    cout << dp[N][W]<<endl;
    return 0;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    char s[3];
    cin>>s;
    if(s[1]=='B')
    s[1]='R';
    else
    s[1]='B';
    cout<<s<<endl;
}

Measured memory_bytes: 3548
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		String[] list = scanner.nextLine().split(" ");

		if(Integer.parseInt(list[0]) <= Integer.parseInt(list[1])) {
			System.out.println("unsafe");
		}else {
			System.out.println("safe");
		}

	}
}

Measured memory_bytes: 35776
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def f(N):
    atk = 0
    if N == 1:
        atk += 1
    else:
        atk += f(N // 2) * 2 + 1
    return atk


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    print(f(N))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3832
#include<stdio.h>

int A[2000000];
int B[2000000];

void Counting_Sort(int k){
  int i,j;
  int C[10001];
  for(i=0;i<10001;i++)C[i]=0;
  for(j=0;j<k;j++)C[A[j]]++;
  for(i=1;i<10001;i++)C[i]+=C[i-1];  
  for(j=k-1;j>=0;j--){
    C[A[j]]--;
    B[C[A[j]]]=A[j];
  }
}

int main(){
  int n,i;
 
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&A[i]);
  Counting_Sort(n);
  for(i=0;i<n;i++){
    if(i)printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 16264
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pii>
#define endl '\n'
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define in insert
#define pi 3.14159265358979323846
#define rep(i,a,b) for(int i = a ; i < b ; i++)
#define repr(i,a,b) for(int i = b ; i > a ; i--) 
  
long long fact(long long a, long long b){
    int r= max(a, b);
    int v= min(a, b);
    int l=1;
    // if(v==0)
    for(int i=r+1; i<=a+b; i++){
        l*=i;
    }
    for(int i=v; i>=2; i--){
        l/=i;
    }
    return l;
}

int gcd(int a, int b) { 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
}

int powr(int a) { 
    int var=1;
    for(int i=0; i<a; i++){
        var*=2;
    }
    return var;
}

signed main(){    
    fast;
    int n;
    cin >> n;
    int a[n];
    // int b[1000001]={};
    rep(i,0,n){
        cin >> a[i];
    }
    sort(a, a+n);
    int b[a[n-1]+1]={};
    int ans=0;
    for(int i=0; i<n; i++){
        if(i!=n && a[i]==a[i+1]){
            int j=a[i];
            while(j<=a[n-1]+1){
                b[j]=1;
                j+=a[i];
            }
            continue;
        }
        int j=a[i];
        if(b[j]==0){
            ans+=1;
            while(j<=a[n-1]+1){
                b[j]=1;
                j+=a[i];
            }
        }
    }
    cout << ans;
}

Measured memory_bytes: 12992
#include <algorithm>
#include <array>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    cout << (k * 2 - 1 <= n ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define gc() getchar()
#define pc(a) putchar(a)
#define int long long
#define inf (1ll<<60)
inline int read()
{
    int x=0,f=1;
    char c=gc();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-f;
        c=gc();
    }
    while(c>='0'&&c<='9') x=x*10+c-'0',c=gc();
    return x*f;
}
int Num[25];
inline void write(int x)
{
    if(!x) {pc('0');return;}
    if(x<0) x=-x,pc('-');
    int top=0;
    while(x) Num[++top]=x%10,x/=10;
    while(top) pc(Num[top--]+'0');
    return;
}
#define ma 300005
int su[ma];
map<int,int> vis;
signed main()
{
	int n=read(),x=read(),m=read();
	int lop=0,ans=0;
	int lopp=0,st=1;
	while(1)
	{
		lop++;
		if(vis[x]) 
		{
			lopp=lop-vis[x],st=vis[x];
			break;	
		}
		ans=(ans+x);
		vis[x]=lop;
		su[lop]=(su[lop-1]+x);
		x=(x*x)%m;
		if(lop>=n)
		{
			lopp=lop;
			break;
		} 
	}
	write((su[st-1]+((n-st+1)/lopp)*(ans-su[st-1])+su[(n-st+1)%lopp+st-1]-su[st-1]));
}









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

int main()
{
    long long A,B,ans;
    string Bi;
    cin>>A>>Bi;
    B=(Bi[0]-'0')*100+(Bi[2]-'0')*10+Bi[3]-'0';

    ans=A*B/100;

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3624
dish=[int(input()) for i in range(5)]

def ceil(v):
    """1桁目を強制切り上げ"""
    if v%10==0:
        return v
    else:
        return v - v%10 + 10

#最大値
min_time = sum(ceil(a) for a in dish)

import itertools

for a,b,c,d,e in list(itertools.permutations(dish)):
    time = ceil(a)
    time = ceil(time+b)
    time = ceil(time+c)
    time = ceil(time+d)
    time += e
    if time < min_time:
        min_time=time
print(min_time)


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

const int MAX_N = 1e5;
int N, K, Q;
int A[MAX_N + 1];

int main() {
    int s[MAX_N + 1];
    memset(s, 0, sizeof(s));
    cin >> N >> K >> Q;

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

    for(int i = 0; i < Q; i++) {
        int x = A[i] - 1;
        s[x] += 1;
    }

    for(int i = 0; i < N; i++) {
        if ( K - Q + s[i] >= 1 ) {
            cout << "Yes" << "\n";
        } else {
            cout << "No" << "\n";
        }
    }
    return 0;
}


Measured memory_bytes: 1408
D = int(input())
c = list(map(int, input().split()))
s = [input().split() for _ in range(D)]
t = [int(input()) for _ in range(D)]
last = [0] * 26  # コンテストを開催した最後の日
v = 0 # 満足度
for d in range(1, D + 1):
    last[t[d - 1] - 1] = d
    v += int(s[d - 1][t[d - 1] - 1])
    for i in range(26):
        v -= c[i] * (d - last[i])
    print(v)


Measured memory_bytes: 74828
#include<stdio.h>
int main(void)
{
	int  d;
	scanf("%d", &d);
	if (d == 22) {
		printf("Christmas Eve Eve Eve\n");
	}
	if (d == 23) {
		printf("Christmas Eve Eve\n");
	}
	if (d == 24) {
		printf("Christmas Eve\n");
	}
	if (d == 25) {
		printf("Christmas\n");
	}
	return 0;
}



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

int main(void)
{
    int S;
    cin >> S;
    int h,m,s;
    h = S / 3600;
    S %= 3600;
    m = S / 60;
    S %= 60;
    s = S;
    cout << h << ":" << m << ":" << s << endl;
}


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


int main(){
  int n;
  cin >> n;
  vector<int> v(n, 0);
  for(int i = 0; i < n; i++){
    cin >> v[i];
  }
  vector<int> color(9, 0);
  for(int i = 0; i < n; i++){
    for(int j = 0; j < 9; j++){
      if(j < 8){
        if(v[i] / 400 == j){
          color[j] = 1;
          break;
        }
      }
      else{
        if(v[i] / 400 >= 8){
          color[8]++;
        }
      }
    }
  }
  int sum = 0;
  for(int i = 0; i < 8; i++){
    sum += color[i];
  }
  if(sum == 0){
    int minc = 1;
    int maxc = n;
    cout << minc << " " << maxc << endl;
  }
  else{
    int minc = sum;
    int maxc;
    maxc = sum + color[8];
    cout << minc << " " << maxc << endl;
  }
  

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(int argc, const char * argv[]) {
    string card;
    int h;
    
    while (1) {
        cin >> card;
        if(card=="-"){
            break;
        }
        cin>>h;
        for(int i=0;i<h;i++){
            int h;
            cin>>h;
            card=card.substr(h)+card.substr(0,h);  //(hから残り全部)+(0からhまで)に入れ替える
        }
        cout << card <<endl;
    }
    return 0;
}


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


const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (t <= 0) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


int main(){
  int s; cin >> s;
  mint dp[s+1], sum = 0;
  dp[0] = 1;
  for(int i = 1; i <= s; i++){
    if(i - 3 >= 0) sum += dp[i - 3];
    dp[i] = sum;
  }
  cout << dp[s] << endl;
  return 0;
}


Measured memory_bytes: 3600
def intRec(h,w):
    diag=h**2+w**2
    minD=1e8
    ans=[]
    for H in range(1,151):
        for W in range(1,151):
            if H<W:
                Diag=H**2+W**2
                if diag==Diag and H>h:
                    return [H,W]
                elif diag<Diag and Diag<minD:
                    minD=Diag
                    ans=[H,W]
    return ans

if __name__=="__main__":
    while True:
        h,w=map(int,input().split())
        if h==0:
            break
        ans=intRec(h,w)
        print(ans[0],ans[1])


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

typedef long long ll;
char buff[105];
bool huiwen(int l,int r){
    for(;l<r;l++,r--){
        if(buff[l]!=buff[r])
            return false;
    }
    return true;
}
int main() {
    scanf("%s",buff+1);
    int len=strlen(buff+1);
    if(huiwen(1,len)&&huiwen(1,(len-1)/2)&&huiwen((len+3)/2,len)) puts("Yes");
    else puts("No");
    return 0;
}

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

int main(void) {
   int N,L;
   cin>>N>>L;
   int min = 10000000;
   for (int i = 0; i < N;i++) {
      if (abs(L+i) < abs(min)) min = L+i;
   }
   // cout<<min<<endl;
   int ans = 0;
   for (int i = 0; i < N;i++) ans += L+i;
   ans -= min;
   cout<<ans<<endl;


   return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int d = sc.nextInt();
    String ans = "No";
    if((a+d-1)/d >= (c+b-1)/b)
      ans = "Yes";
    
    System.out.println(ans);
  }
}


Measured memory_bytes: 35760
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        int sum = 0;
        for (int i = 0; i < a.length(); i++) {
            sum = sum + (a.charAt(i) - '0');
        }
        if (sum % 9 == 0)
            System.out.println("Yes");
        else
            System.out.println("No");
        sc.close();
    }
}

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

using namespace std;

int main()
{
  int wonCount = 0;
  string s;
  cin >> s;
  for (const auto c : s) {
    if (c == 'o') {
      wonCount++;
    }
  }
  int possibleWonCount = 15 - int(s.size());
  
  if (wonCount + possibleWonCount >= 8) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _GLIBCXX_DEBUG
#define rep(i, c) for (int i = 0; i < (int)c; i++)
#define debug(x) cout << #x << " = " << x << endl
#define print(x) cout << x << endl;
const ll MOD = 1000000007;

int main()
{
    int A, B, C, K;
    cin >> A >> B >> C >> K;

    if (K < A)
    {
        cout << K << endl;
    }

    else if (K <= A + B)
    {
        cout << A << endl;
    }

    else
    {
        cout << A - (K - A - B) << endl;
    }
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll ;
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
 const ll inf=1e9+7;

int main()
{
    fast;
    
 ll n,k,x,y;
 cin>>n>>k>>x>>y;
 
 ll ans;
 
 ans=min(k,n)*x+(max(n-k,0LL) )*y;
 
 cout<<ans;
    
   
}

		
	
	
	
	


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

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

   if ((n % 500) <= a) {
       cout << "Yes" << endl;
   } else {
       cout << "No" << endl;
   }
}

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

const int MAXN = 1e6 + 10;
int n, pr[MAXN], a[MAXN];

void div(int x)
{
	for (int i = 2; i*i <= x; i++)
	{
		if (x%i == 0)
		{
			pr[i] += 1;
			while (x%i == 0)
				x /= i;
		}
	}
	if (x > 1)
		pr[x] += 1;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		div(a[i]);
	}
	int flag = 0;
	for (int i = 1; i <= 1e6; i++)
	{
		if (pr[i] > 1)
			flag = 1;
		if (pr[i] == n)
		{
			flag = 2;
			break;
		}
	}
	if (flag == 0)
		printf("pairwise coprime\n");
	else if (flag == 1)
		printf("setwise coprime\n");
	else
		printf("not coprime\n");
	return 0;
}


Measured memory_bytes: 11328
#include <bits/stdc++.h>
typedef long long ll;

#define pll pair<ll,ll>
#define ff first
#define snd second
#define pb push_back
#define vll vector<ll>
#define vpll vector<pll>
#define endl "\n"
#define MOD 1000000007
using namespace std;

ll const N = 1e5+1;

int f(ll x,ll y)
{
        while((x%y)==0)
        {
                x/=y;
        }
        return ((x%y)==1);
}

void solve()
{
   ll n;
   cin>>n;
   ll ans = 0;
   
   if(n==2)
   {
           cout<<1;
           return;
   }
   
   for(ll i=1;i*i<=n;i++)
   {
           if(i==1)
           {
                ans++;
                continue;
           }
           if(n%i==0)
           {
                   if(i*i==n)
                   {
                        ans+=f(n,i);   
                   }
                   else
                   {
                           ans+=f(n,i);
                           ans+=f(n,n/i);
                   }
           }
   }
   n--;
   for(ll i=1;i*i<=n;i++)
   {
           if(i==1)
           {
                   ans++;
                   continue;
           }
           if(n%i==0)
           {
                   if(i*i==n)
                   {
                        ans++;   
                   }
                   else
                   {
                           ans+=2;
                   }
           }
   }
   
   cout<<ans;
}
 
int main() {
            ios_base::sync_with_stdio(false);
            cin.tie(NULL);
	    int t=1;
	    //cin>>t;
	    while(t--)
	    {
	            solve();
	    }
	    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
#include <cmath>
 
using namespace std;
 
#define F first
#define S second
 
#define X real()
#define Y imag()
 
#define EPS (1e-7)
 
typedef complex<double> Point;
typedef vector<Point> Polygon;
typedef pair<double, Point> Circle;
 
bool isPointInCircle(const Point& p, const Circle& c) {
  if(abs(p-c.S) < abs(c.F) + EPS) return true;
  return false;
}
 
double dot(const Point& a, const Point& b) {
  return a.X*b.X+a.Y*b.Y;
}
 
double cross(const Point& a, const Point& b) {
  return a.X*b.Y-a.Y*b.X;
}
 
typedef pair<Point, Point> Segment;
typedef Segment Line;
 
double distanceLP(Line l, Point p) {
  return abs(cross(l.S-l.F, p-l.F)) / abs(l.S-l.F);
}
 
double distanceSP(Segment s, Point p) {
  Point a = s.F, b = s.S;
   
  if(dot(b-a, p-a) < EPS) return abs(p-a);
  if(dot(a-b, p-b) < EPS) return abs(p-b);
  return distanceLP(s, p);
}
 
 
enum struct ECont { OUT, ON, IN };
ECont contains(const Polygon& poly, const Point& p) {
  bool in = 0;
  for(int i=0; i<poly.size(); i++) {
    Point a = poly[i] - p, b = poly[(i+1)%poly.size()] - p;
    if(a.imag() > b.imag()) swap(a, b);
    if(a.imag() <= 0 && 0 < b.imag()) {
      if(cross(a, b) < 0) in = !in;
    }
    if(cross(a, b) == 0 && dot(a, b) <= 0) return ECont::ON;
  }
   
  return in ? ECont::IN : ECont::OUT;
}
 
int main() {
   
  while(1) {
    Polygon points(3);
    Circle circle;
   
    for(int i=0; i<3; i++) {
      double x, y; cin >> x >> y;
      if(x == 0) return 0;
     
      points[i] = Point(x, y);
    }
   
    {
      double x, y; cin >> x >> y;
      circle.S = Point(x, y);
      cin >> circle.F;
    }
   
    bool ok = 1;
    for(int i=0; i<3; i++) {
      ok &= isPointInCircle(points[i], circle);
    }
    if(ok) {
      cout << 'b' << endl;
      continue;
    }
     
    int uncross = 0;
    for(int i=0; i<3; i++) {
      Segment seg = make_pair(points[(i+1)%3], points[i]);
      uncross += circle.F < distanceSP(seg, circle.S) + EPS;
    }
    if(uncross == 3) {
      int flg = 0;
      for(int i=0; i<3; i++) {
        if(contains(points, circle.S) == ECont::IN) {
        //if(dot(points[(i+1)%3]-points[i], circle.S-points[i]) * dot(points[(i+2)%3]-points[(i+1)%3], circle.S-points[(i+1)%3]) > 0) {
          flg ++;
        }
      }
      if(flg == 3) { cout << 'a' << endl; continue; }
    }
 
    int cross = 0;
    for(int i=0; i<3; i++) {
      Segment seg = make_pair(points[(i+1)%3], points[i]);
      cross += distanceSP(seg, circle.S) <= circle.F + EPS;
    }
    if(cross > 0) cout << 'c' << endl;
    else cout << 'd' << endl;
  }
   
  return 0;
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
//登録しよう！→ https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define gre greater //sortを降順にする
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示

void solve(long long N, std::vector<long long> A, std::vector<long long> B){
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    ans += min(A[i],B[i]);
    if(A[i] < B[i]){
      ans += min(B[i]-A[i] , A[i+1]);
      A[i+1] -= min(B[i]-A[i] , A[i+1]);
    }
  }
  cout << ans << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N+1);
    for(int i = 0 ; i < N+1 ; i++){
        scanf("%lld",&A[i]);
    }
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&B[i]);
    }
    solve(N, std::move(A), std::move(B));
}


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

int main() {
  int a;
  string s;
  
  cin >> a >> s;
  
  if (a >= 3200) {
    cout << s << endl;
  }
  else if (a < 3200) {
    cout << "red" << endl;
  }
}


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

int main () {
    int k, s;
    std::cin >> k >> s;

    long long ans = 0;
    for (int x = 0; x <= k; x++)
    {
        for (int y = 0; y <= k; y++) {
            int z = s - x - y;
            if(z >= 0 && z <= k) {
                ans++;
            }
        }
    }

    std::cout << ans << "\n";
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define per(i,n) for(int i = n; i >= 0; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }



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

  string s;
  cin >> s;
  rep(i,sz(s)) {
    if(s[i] == ',') cout << ' ';
    else cout << s[i];
  }
  cout << endl;
}

Measured memory_bytes: 256
def main():
    a, b, c, d = map(int, input().split())
    while a >= 0 and c >= 0:
        c -= b
        if c <= 0:
            print("Yes")
            exit()
        a -= d
        if a <= 0:
            print("No")
            exit()


if __name__ == '__main__':
    main()


Measured memory_bytes: 61792
program test
implicit none
integer :: i,j,k,m,n,ans
 
read(*,*) n

ans = 0

do i= 0,25
do j =0,25
if(4*i + 7*j == n) then
ans =1
endif
enddo
enddo

if(ans == 1) then
write(*,*) 'Yes'
else
write(*,*) 'No'
endif


end program

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;



long long func( long long a, long long b, long long p ) {
    if ( b == 0 ) {
        return 1;
    }
    else if ( b%2 == 0 ) {
        long long temp = func( a, b/2, p );
        return (temp * temp)%p;
    }
    else {
        return ( func( a, b-1, p ) * a ) % p;
    }
    
}



int main() {
    
    int N;
    cin >> N;
    vector<int> A(N+1), B(N+1);
    vector<long long> F(N+2);
    
    long long f = 1;
    F[0] = 1;
    for ( int i = 1; i <= N+1; i++ ) {
        f *= i;
        f %= MOD;
        F[i] = f;
    }
    
    
    for ( int i = 0; i < N+1; i++ ) {
        cin >> A[i];
        B[i] = A[i];
    }
    sort( B.begin(), B.end() );
    int a;
    for ( int i = 1; i < N+1; i++ ) {
        if ( B[i] == B[i-1] ) { a = B[i]; }
    }
    
    int i1 = -1,i2;
    for ( int i = 0; i < N+1; i++ ) {
        if ( A[i] == a ) {
            if ( i1 == -1 ) { i1 = i; }
            else { i2 = i; }
        }
    }
    
    int x = i1 + N-i2;
    
    
    for ( int i = 1; i <= N+1; i++ ) {
        
        long long c = ( ( F[N+1] * func( F[N+1-i], MOD-2, MOD ) )%MOD * func( F[i], MOD-2, MOD ) )%MOD;
        
        if ( x >= i-1 ) {
            long long d = ( ( F[x] * func( F[x-i+1], MOD-2, MOD ) )%MOD * func( F[i-1], MOD-2, MOD ) )%MOD;
            c = ( c + MOD - d )%MOD;
        }
        
        cout << c << endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 2816
# Author: cr4zjh0bp
# Created: Sat Mar 28 10:36:41 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import defaultdict

a = nan(3)
d = [[0] * 3 for _ in range(3)]
n = ni()
b = nin(n)
dic = defaultdict(int)

for i in range(n):
    dic[b[i]] += 1

for i in range(3):
    for j in range(3):
        d[i][j] = dic[a[i][j]] >= 1

flag = False
for i in range(3):
    cnt = 0
    for j in range(3):
        cnt += d[i][j]
    if cnt == 3:
        flag = True

for i in range(3):
    cnt = 0
    for j in range(3):
        cnt += d[j][i]
    if cnt == 3:
        flag = True

cnt_r = 0
cnt_l = 0
for j in range(3):
    cnt_r += d[j][j]
    cnt_l += d[j][3 - j - 1]
if cnt_r == 3 or cnt_l == 3:
    flag = True

print("Yes" if flag else "No")

Measured memory_bytes: 3316
#include<stdio.h>
int main(){
  int i,j,N,S,c=0;
  int A[100];
  scanf("%d",&N);
 
  for (i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  for(j=0;j<N;j++){
    for(i=N-1;i>0;i--){
      if(A[i]<A[i-1]){
	S=A[i-1];
	A[i-1]=A[i];
	A[i]=S;
	c++;
      }
    }
  }
  for(i=0;i<N-1;i++){
    printf("%d ",A[i]);
  }
  printf("%d\n",A[i]);
  printf("%d\n",c);	 
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())
#define CLR(a) memset((a), 0, sizeof(a))
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

//using LL = long long;
using namespace std;

const int dy[] = {0, 0, 1, -1};
const int dx[] = {1, -1, 0, 0};
const double EPS = 1e-10;
const double PI = acos(-1.0);

void seliction_Sort(vector<int> v, int n){
    int mini, count = 0;
    for (int i = 0; i < n - 1; i++)
    {
        mini = i;
        for (int j = i + 1; j < n; j++)
        {
            if (v[j] < v[mini])
                mini = j;
        }

        if (i != mini)
        {
            count++;
            swap(v[i], v[mini]);
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl
         << count << endl;
}


int main()
{
    int n;
    cin >> n;
    vector<int> v;
    
    for (int temp; cin >> temp;)
    {
        v.push_back(temp);
    }

    seliction_Sort(v, n);

        return 0;
}


Measured memory_bytes: 3156
d = int(input())
*C, = map(int, input().split())
S = [list(map(int, input().split())) for i in range(d)]
X = [int(input()) - 1 for i in range(d)]
L = [-1 for j in range(26)]
score = 0
for i in range(d):
    L[X[i]] = i
    score += S[i][X[i]]
    score -= sum([C[j] * (i - L[j]) for j in range(26)])
    print(score)


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

int main() {
  ll x; cin >> x;
  cout << x / 500 * 1000 + (x % 500 / 5 * 5);
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main(void) {
	int N;
	scanf("%d", &N);
	int count[N+1];
	for(int i = 0 ; i <= N ; i++){
		count[i] = 0;
	}
	for(int i = 2 ; i <= N ; i = i+2){
		int number = 0;
		int j = i;
		while(j % 2 == 0){
			number++;
			j /= 2;
		}
		count[i] = number;
	}
	int Max, Maxindex = 1;
	for(int i = 0 ; i <= N ; i++){
		if(Max < count[i]){
			Max = count[i];
			Maxindex = i;
		}
	}
	printf("%d\n", Maxindex);
}

Measured memory_bytes: 128
import java.util.Scanner;
import java.lang.Math;

class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int c = stdIn.nextInt();
		int k;
		if (c <= a + b + 1) {
			k = b + c;
		} else {
			k = a + 2 * b + 1;
		}
		System.out.println(k);
	}
}

Measured memory_bytes: 22996
#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <vector>
typedef long long ll;
using namespace std;

int main(){
    int a, b; char op;
    cin >> a >> op >> b;
    cout << (op=='+' ? a+b : a-b) << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import Counter
n,k,q=map(int,input().split())
a_list=[int(input()) for i in range(q)]
S=Counter(a_list)
for i in range(1, n+1):
    score=k-q+S[i]
    if score>0:
        print("Yes")
    else :
        print("No")
    

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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

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

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int w, a, b;

int main() {
	cin >> w >> a >> b;
	if (a<b) cout << max(b-a-w, 0) << ln;
	else cout << max(a-b-w, 0) << ln;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#define ll long long
#define inf 1e9+5
using namespace  std;

int main(){

	string s,t;
	cin>>s>>t;

	ll i,j;

	ll dp[s.length()+1][t.length()+1];

	for(i=0;i<=s.length();i++){
		for(j=0;j<=t.length();j++){
			if(i==0||j==0){
				dp[i][j]=0;
			}else{
				if(s[i-1]==t[j-1]){
					dp[i][j] = dp[i-1][j-1]+1;
				}else{
					dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
	}

	ll l=dp[s.length()][t.length()];
	//cout<<l<<endl;
	string lcs;
	
	i=s.length(),j=t.length();
	while(i>0 && j>0){
		if(s[i-1]==t[j-1]){
			lcs.push_back(s[i-1]);
			i--;
			j--;
		}

		else if(dp[i-1][j]>dp[i][j-1]){
			i--;
		}else{
			j--;
		}
	}
	reverse(lcs.begin(),lcs.end());

	cout<<lcs<<endl;



	return 0;
}

Measured memory_bytes: 73980
from collections import deque

s = input()
q = int(input())

deq = deque([s])
flag = 1
for i in range(q):
    query = input().split()
    if query[0]==str(1):
        flag*=-1 
    if query[0]==str(2):
        x = 1 if query[1]==str(1) else -1
        if flag*x==1:
            deq.appendleft(query[2])
        else:
            deq.append(query[2])

if flag==-1:
    print(''.join(deq)[::-1])
else:
    print(''.join(deq))

Measured memory_bytes: 93124
#include<bits/stdc++.h>
#define N (100009)
using namespace std;

char s[N];

int main()
{
	cin>>s+1;
	for (int i=1,l=strlen(s+1); i<=l; ++i)
	{
		if (i-1>=1 && s[i-1]==s[i]) {cout<<i-1<<' '<<i<<endl; return 0;}
		if (i-2>=1 && s[i-2]==s[i]) {cout<<i-2<<' '<<i<<endl; return 0;}
	}
	cout<<-1<<' '<<-1<<endl;
}

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

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;

ll N, K;
int main() {
	cin >> N >> K;
	if (K % 2 == 1) {
		ll a = N / K;
		cout << a * a * a << endl;
	}else{
		ll a = (N / K), b = (N / K) + (N - N/K*K) / (K/2);
		cout << a * a * a + b * b * b << endl;
	}
	return 0;
}


Measured memory_bytes: 3620
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int D;
	scanf("%d", &D);
	int c[26], s[D][26], last[26], ans[D];
	for (int i = 0; i < 26; ++i) scanf("%d", &c[i]);
	for (int i = 0; i < D; ++i) {
		for (int j = 0; j < 26; ++j) scanf("%d", &s[i][j]);
	}
	int bst = 0, ok = 0;
	for (int h = 0; h < 13; ++h) {
		fill_n(last, 26, -1);
		int sav = 0;
		for (int i = 0; i < D; ++i) {
			int x = 0, opt = 0;
			for (int j = 0; j < 26; ++j) {
				if (c[j] * (i - last[j] + h) + s[i][j] > x) x = c[j] * (i - last[j] + h) + s[i][j], opt = j;
			}
			sav += c[opt] * (i - last[opt]) + s[i][opt];
			last[opt] = i;
		}
		if (sav > bst) bst = sav, ok = h;
	}
	fill_n(last, 26, -1);
	for (int i = 0; i < D; ++i) {
		int x = 0, opt = 0;
		for (int j = 0; j < 26; ++j) {
			if (c[j] * (i - last[j] + ok) + s[i][j] > x) x = c[j] * (i - last[j] + ok) + s[i][j], opt = j;
		}
		last[opt] = i;
		ans[i] = opt;
	}
	for (int i = 0; i < D; ++i) printf("%d\n", ans[i] + 1);
	return 0;
}

Measured memory_bytes: 1772
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
#define int long long int
void YESNO(bool), YesNo(bool);
template <class T1, class T2>
bool chmin(T1 &l, const T2 &r);
template <class T1, class T2>
bool chmax(T1 &l, const T2 &r);
int color[200005] = {};
vector<int> e[200005];
bool is_bipartiy(int u, int col)
{
  if (color[u] != -1)
    return col == color[u];
  color[u] = col;
  for (auto s : e[u])
  {
    if (!is_bipartiy(s, 1 - col))
      return false;
  }
  return true;
}
void solve(long long N, long long M, std::vector<long long> A,
           std::vector<long long> B)
{
  rep(i, N) color[i] = -1;
  rep(i, M) e[A[i] - 1].push_back(B[i] - 1), e[B[i] - 1].push_back(A[i] - 1);
  if (!is_bipartiy(0, 0))
  {
    cout << N * (N - 1) / 2 - M << endl;
    return;
  }

  lli blue = 0;
  rep(i, N)
  {
    if (color[i])
      blue++;
  }
  cout << blue * (N - blue) - M << endl;
}

signed main()
{
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  std::vector<long long> A(M);
  std::vector<long long> B(M);
  for (int i = 0; i < M; i++)
  {
    scanf("%lld", &A[i]);
    scanf("%lld", &B[i]);
  }
  solve(N, M, std::move(A), std::move(B));
  return 0;
}

// -- lib
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }

template <class T1, class T2>
bool chmin(T1 &l, const T2 &r)
{
  return (l > r) ? (l = r, true) : false;
}

template <class T1, class T2>
bool chmax(T1 &l, const T2 &r)
{
  return (l < r) ? (l = r, true) : false;
}


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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

//-----------------------------------------------------------------------------

int n,k,x,y;
char c;
int imos[5010][5010];

int calc(int y,int x) {
	int res=0;
	if(y>=0&&x>=0) res=imos[min(k*2-1,y)][min(k*2-1,x)];
	return res;
}

int sum(int y,int x) {
	return calc(y,x)-calc(y-k,x)-calc(y,x-k)+calc(y-k,x-k);
}

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

	cin>>n>>k;
	REP(i,n) {
		cin>>x>>y>>c;
		if(c=='W') x+=k;
		int nx=x%(2*k),ny=y%(2*k);
		imos[ny][nx]++;
	}
	REP(i,k*2) REP(j,k*2) imos[i][j]+=calc(i-1,j);
	REP(i,k*2) REP(j,k*2) imos[i][j]+=calc(i,j-1);
	/*cout<<endl;
	REP(i,k*2) {
		REP(j,k*2) cout<<imos[i][j]<<' ';
		cout<<endl;
	}*/
	int ans=0;
	REP(i,k*2) {
		REP(j,k*2) {
			ans=max(ans,sum(i,j)+sum(i-k,j-k)+sum(i-k,j+k)+sum(i+k,j-k)+sum(i+k,j+k)+sum(i+2*k,j)+sum(i,j+k*2));
		}
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 40448
#include<stdio.h>
int main(void)
{
	int n,i,j,k,d,c;
	while(scanf("%d",&n)!=EOF){
		c=0;
		for(i=0;i<10;i++){
			for(j=0;j<10;j++){
				for(k=0;k<10;k++){
					for(d=0;d<10;d++){
						if(i+j+k+d==n){
							c++;
						}
					}
				}
			}
		}
		printf("%d\n",c);	
	}
	return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
int N, M;
int X[101010];
int L[101010];

int main()
{
    cin >> N >> M;
    rep(i, 0, M)
    {
        cin >> X[i];
    }
    sort(X, X + M);
    rep(i, 0, M - 1)
    {
        L[i] = X[i + 1] - X[i];
    }
    sort(L, L + M - 1, greater<int>());
    ll Lsum = 0;
    rep(i, 0, N - 1)
    {
        Lsum += L[i];
    }
    cout << X[M - 1] - X[0] - Lsum << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
    string s;
    int k;
    cin >> s >> k;
    set<string> se;
    int i,j;
    for(i = 0;i < s.size();++i){
        for(j = 1;j <= k;++j){
            se.insert(s.substr(i,j));
        }
    }
    vector<string> array;
    for(string x: se){
        array.push_back(x);
    }
    sort(array.begin(),array.end());
    cout << array.at(k-1) << endl;
    return 0;
}


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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::bitset;

#define rep(i,n)    for(int i=0; i<(int)(n); i++)
#define reps(i,s,e) for(int i=s; i<(int)(e); i++)
#define coutd(i) cout << std::fixed << std::setprecision(i)
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;

template<class T>
using Set = std::set<T>;
template<class T, class U>
using Map = std::map<T, U>;

template<class T>
using Graph = vector<vector<T>>;

const int INT_BIG = 1<<28;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    int rootNum;

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
        rootNum = N;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    constexpr int getRootNum() noexcept {
        return rootNum;
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        rootNum--;
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    rep(i, M) {
        int x, y;
        cin >> x >> y;
        uf.unite(x-1,y-1);
    }
    vint num(N, 0);
    rep(i, N) {
        num[uf.root(i)]++;
    }
    int max = 0;
    rep(i, N) {
        if (max < num[i]) {
            max = num[i];
        }
    }
    cout << max << endl;
}

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

typedef long long ll;

int32_t main(){
	int n , l ;
	cin >> n >> l ;
	int a[n] , minval = INT_MAX , val ;
	for(int i = 0 ; i < n ; i++){
		a[i] = l + i ;
		if(minval > abs(a[i])){
			minval = abs(a[i]) ;
			val = a[i] ;
		}
	}
	cout << accumulate(a,a+n,0) - val ;

 	return 0;
}



Measured memory_bytes: 256
use strict;
use warnings;
use utf8;
use Data::Dumper;

use feature qw(say);

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

my $list_array = [split/ /, $list];

my $i = 1;
for my $num (@$list_array) {
    if ($num == 0) {
        say $i;
    }
    $i++;
}


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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

int main(void)
{
  ll a= 0;
  string s;
  cin >> s;
  REP(i, 4) {
    if(s[i]=='+') a++;
    else a--;
  }
  cout << a << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	long N;
	cin >> N;
  	long R[N];
  	int idx = 0;
  	int minR_idx = 0;
  	int maxR_idx = 0;
  	bool flag = false;
  	long max_benefit = -1000000001;
  	while(cin >> R[idx])
    {
	  if(flag)
      {
        flag = false;
        maxR_idx = minR_idx;
      }
      if(R[minR_idx] >= R[idx])
      {
        flag = true;
        minR_idx = idx;
      }
      if(R[maxR_idx] <= R[idx])
      {
        maxR_idx = idx;
      }
      if(minR_idx != maxR_idx)
      {
        long benefit;
        if(minR_idx > maxR_idx)
        {
          benefit = R[minR_idx] - R[maxR_idx];
        }
        else
        {
          benefit = R[maxR_idx] - R[minR_idx];
        }
        if (max_benefit < benefit) max_benefit = benefit;
      }
      else if(minR_idx != 0 && maxR_idx != 0 && minR_idx == maxR_idx && max_benefit < 0)
        max_benefit = 0;
      idx++;
    }
	cout << max_benefit << endl;
  	return 0;
}



Measured memory_bytes: 4776
use proconio::input;
use proconio::marker::{Bytes, Chars, Isize1, Usize1};

fn main() {
    input! {
        n: usize,
        k: usize,
        v: [usize; n], // v_1 v_2 ... v_n
    }

    for i in 0..n-k {
        if v[k+i] > v[i] {
            println!("Yes")
        } else {
            println!("No")
        }
    }
}


Measured memory_bytes: 5596