akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> par, rank;
    UnionFind(int size) {
        par.resize(size);
        rank.resize(size);
        for (int i = 0; i < size; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

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

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

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

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

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf = UnionFind(n);
    for (int i = 0; i < m; i++) {
        int s, t;
        cin >> s >> t;
        uf.unite(s, t);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        if (uf.same(s, t)){
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3564
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    m1,d1=map(int,input().split())
    m2,d2=map(int,input().split())
    print(0 if(d2-d1==1) else 1)
resolve()

Measured memory_bytes: 38384
/*
   Username : moondancer
   Name : Moon Dancer
*/


#include <bits/stdc++.h>
using namespace std;

#define int long long

string x;
int dp[10005][101][2];
const int mod=1e9+7;
int d;

int dfs(int i,int sum, bool smaller){
    if(i==(int)x.size()){
        return (sum%d == 0);
    }
    if(dp[i][sum][smaller] != -1){
        return dp[i][sum][smaller];
    }

    int lower_limit, upper_limit;
    if(i==0) lower_limit=1;
    else lower_limit=0;
    int t=x[i]-'0';
    if(smaller) upper_limit=9;
    else upper_limit=t;


    int ans=0;
    for(int digit=0; digit<=upper_limit; ++digit){
        int t=x[i]-'0';
        bool f=smaller;
        if(digit < t){
            // smaller|=1;
            f|=1;
        }
        ans=(ans+dfs(i+1,(sum+digit)%d,f))%mod;
    }
    return dp[i][sum][smaller]=ans;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>x>>d;
    for(int i=0; i<=10000; ++i){
        for(int j=0; j<=100; ++j){
            for(int k=0; k<=1; ++k){
                dp[i][j][k]=-1;
            }
        }
    }
    // memset(dp, sizeof(dp), -1);
    // cout<<x.size();
    cout<<(dfs(0,0,0)-1+mod)%mod;
    return 0;
}

Measured memory_bytes: 20104
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
S = ['_']+list(input())

ans = 0
for i in range(1, N+1):
    if S[i-1]!=S[i]:
        ans += 1
print(ans)

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


int main() {
    string s;
    cin >> s;
    if((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3])){
        cout << "Yes\n";
    }else cout << "No\n";
    return 0;
}
/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
# A - Biscuits
# https://beta.atcoder.jp/contests/agc017/tasks/agc017_a

# A_Biscuits.py

import math

N, P = map(int,input().strip().split(" "))
A = list(map(int,input().strip().split(" ")))

even = 0
odd = 0
for a in A:
    if a % 2 == 0:
        even += 1
    else:
        odd += 1

even_combi = 2 ** even

odd_combi = 0
m = int(odd/2)
#print("m:", m)
for i in range(m+1):
    if P == 0:
        odd_combi += math.factorial(odd) / (math.factorial(i*2) * math.factorial(odd-i*2))
    else:
        if odd-(i*2+1) > 0:
            odd_combi += math.factorial(odd) / (math.factorial(i*2+1) * math.factorial(odd-(i*2+1)))

#print(even_combi, odd_combi)
print(int(even_combi*odd_combi))


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int n;
long long f[87];
int main()
{
    cin>>n;
    f[0]=2;
    f[1]=1;
    for(int i=2;i<=n;i++)
        f[i]=f[i-1]+f[i-2];
    cout<<f[n];
}

Measured memory_bytes: 384
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int cul(int A, int B, int C, int D, char sym1, char sym2, char sym3)
{
	if (sym1 == '+') {
		A += B;
	}
	else {
		A -= B;
	}

	if (sym2 == '+') {
		A += C;
	}
	else {
		A -= C;
	}

	if (sym3 == '+') {
		A += D;
	}
	else {
		A -= D;
	}

	return A;
}

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

	D = N % 10;
	C = (N - D) / 10 % 10;
	B = (N - D - C) / 100 % 10;
	A = (N - D - C - B) / 1000;
	
	char sym[2] = { '+', '-' };
	int num;

	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				
				num = cul(A, B, C, D, sym[i], sym[j], sym[k]);
				if (num == 7) {
					cout << A << sym[i] << B << sym[j] << C << sym[k] << D << "=7" << endl;
					return 0;
				}
			}
		}
	}

    return 0;
}

Measured memory_bytes: 256
//AnkitCode99 here....
#include<bits/stdc++.h>
#define endl "\n"
typedef long long int ll;
#define MOD 1000000007
#define mp make_pair
#define pll pair<ll,ll>
#define pb push_back
//max xor btw range of two numbers..
#define max_XOR(a,b) (1 << int(log2(a ^ b) + 1)) - 1
#define vl vector<ll>
#define inf ll(1e18)
#define all(v) v.begin(),v.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(long long int i=a;i<b;i++)
#define nrep(i,a,b) for(long long int i=a;i>=b;i--)
#define ceil(a,b) a/b+((a%b ==0 )?0:1)
using namespace std;

const ll sz=100005;
const ll szz=1000006;

int main()
{
	fast;
    ll a,b,c;
    cin>>a>>b>>c;
    
    if((a==b and b!=c)||(a==c and b!=c)||(b==c and c!=a))
    	cout<<"Yes";
    else
    	cout<<"No";

}
//Goodbye...

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author crypter_472
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;

class DAnInvisibleHand {
public:
	void solve(std::istream &in, std::ostream &out) {
		int n, t;
		in >> n >> t;
		vector<int> arr(n);
		for (int i = 0; i < n; i++)
			in >> arr[i];
		map<int, set<int>> mp;
		vector<int> mx(n);
		mx[n - 1] = n - 1;
		for (int i = n - 2; i >= 0; i--) {
			if (arr[i] >= arr[mx[i + 1]])
				mx[i] = i;
			else
				mx[i] = mx[i + 1];
		}
		for (int i = 0; i < n; i++) {
			mp[arr[mx[i]] - arr[i]].insert(mx[i]);
		}
		out << (mp.rbegin())->second.size() << '\n';
	}
};


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	DAnInvisibleHand solver;
	std::istream &in(std::cin);
	std::ostream &out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 15104
N=int(input())
mod=10**9+7
memo=[{} for _ in range(N+1)]

def ok(x,y,z,nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def dfs(idx,lis):
    if idx==N:
      return 1
    x,y,z=lis[0],lis[1],lis[2]
    if (x,y,z) in memo[idx]:
        return memo[idx][(x,y,z)]
    ret=0
    for nx in ['A','G','C','T']:
        if ok(x,y,z,nx):
            ret+=dfs(idx+1,(y,z,nx))
    memo[idx][(x,y,z)]=ret%mod
    return ret%mod

print(dfs(0,'DDD'))

Measured memory_bytes: 9616
#include<iostream>
#include<vector>
#include<cstdio>
#include<set>
using namespace std;
int main(){
    set<char> s{'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    string str;
    cin >> str;
    for(int i=0;i<str.size();i++)   s.erase(str[i]);
    if(s.size()==0) cout << "None";
    else    cout << *s.begin();
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
	int n;
	cin >> n;
	map<string, int> mp;
	string s;
	REP(i,n){
		cin >> s;
		mp[s]++;
	}
	int m;
	cin >> m;
	REP(i,m){
		cin >> s;
		mp[s]--;
	}
	int ans = 0;
	for(auto i : mp){ //foreach
		ans = max(ans, i.second);
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
def dfs(cur, visited):
    if visited == (1 << N) - 1:
        return 1
    res = 0
    for to in graph[cur]:
        if not (visited >> to) & 1:
            res += dfs(to, visited | (1 << to))
    return res
print(dfs(0, 1))


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

int h,w;
int vis[405][405],g[405][405];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
pair<int,int> bfs(int sx,int sy){
	int black=0,white=0;
	queue<pair<int,int> >q;
	q.push({sx,sy});
	vis[sx][sy]=1;
	while(!q.empty()){
		pair<int,int>f=q.front();q.pop();
		int x=f.first;
		int y=f.second;
		int p=g[x][y];
		if(p==0)black++;
		else white++;
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>=0 and xx<h and yy>=0 and yy<w){
				int pp=g[xx][yy];
				if(1-pp==p and !vis[xx][yy]){
					vis[xx][yy]=1;
					q.push({xx,yy});
				}
			}
		}
	}
	return make_pair(black,white);
}

int main(){ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>h>>w;

for(int i=0;i<h;i++){
	for(int j=0;j<w;j++){
		char c;cin>>c;
		g[i][j]=(c=='.');
	}
}
long long ans=0;
for(int i=0;i<h;i++){
	for(int j=0;j<w;j++){
		if(!vis[i][j]){
			pair<int,int> f=bfs(i,j);
			ans+=1LL*f.first*f.second;
		}
	}
}
cout<<ans;
return 0;
}


Measured memory_bytes: 1536
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
#include<deque>

using namespace std;
typedef long long ll;

int main(void)
{
    ll X, A;
    cin >> X >> A;

    if(X < A) cout << 0 << endl;
    else cout << 10 << endl;
}

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

#define fs first
#define sc second

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; }


// std::vector Declaration
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// std::vector Initialization
template<typename T>
void fill_all(T& arr, const T& v) { arr = v; }
template<typename T, typename U>
void fill_all(T& arr, const U& v) { for (auto& i : arr) fill_all(i, v); }

// std::vector Debug
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    bool a = 1;
    for (auto e : v) {
        os << (a ? "" : " ");
        os << e;
        a = 0;
    }
    os << "]";
    return os;
}

// std::deque Debug
template<typename T>
ostream& operator<<(ostream& os, const deque<T>& d) {
    os << "[";
    bool a = 1;
    for (auto e : d) {
        os << (a ? "" : " ");
        os << e;
        a = 0;
    }
    os << "]";
    return os;
}

// std::pair Debug
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << " " << p.second << ")";
    return os;
}

// std::set Debug
template<typename T>
ostream& operator<<(ostream& os, const set<T>& st) {
    os << "{";
    bool a = 1;
    for (auto e : st) {
        os << (a ? "" : " ");
        os << e;
        a = 0;
    }
    os << "}";
    return os;
}

// std::multiset Debug
template<typename T>
ostream& operator<<(ostream& os, const multiset<T>& st) {
    os << "{";
    bool a = 1;
    for (auto e : st) {
        os << (a ? "" : " ");
        os << e;
        a = 0;
    }
    os << "}";
    return os;
}

// std::map Debug
template<typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& mp) {
    os << "{";
    bool a = 1;
    for (auto e : mp) {
        os << (a ? "" : " ");
        os << e.first << ":" << e.second;
        a = 0;
    }
    os << "}";
    return os;
}

// std::tuple Debug
template<int N, class Tuple>
void out(ostream& os, const Tuple& t){}
template<int N, class Tuple, class H, class ...Ts>
void out(ostream& os, const Tuple& t) {
    if (N) os << " ";
    os << get<N>(t);
    out<N+1,Tuple,Ts...>(os, t);
}
template<class ...Ts>
ostream& operator<<(ostream& os, const tuple<Ts...>& t) {
    os << "(";
    out<0,tuple<Ts...>,Ts...>(os, t);
    os << ")";
    return os;
}

// Debug
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl


struct edge { int to, cost; };
ostream& operator<<(ostream& os, const edge& e) {
    os << "(" << e.to << ", " << e.cost << ")";
    return os;
}

const LL LINF = 1LL<<60;
const int IINF = 1<<30;
const LL MOD = 1e9+7;

int main()
{
    int k, x; cin >> k >> x;

    for (int i = x-k+1; i <= x+k-1; ++i) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}


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

int main(){
	int n, m;
	string s;
	while(cin >> n >> s){
		int ans = 1;
		for(int i = 0; i < n - 1; i++){
			if(s[i] != s[i+1])
				ans++;
		}
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 512
n, m = map(int, input().split())
a = list(map(int, input().split()))

comp = 1 / (4 * m)
total = 0
suma = sum(a)
for i in range(n):
    if a[i] / suma >= comp:
        total += 1
if total >= m:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int i,j;
 main()
{
  int n;
  cin>>n;
  int a[n]; int b[50000];
  for(i=0;i<n;i++)
  {
      cin>>a[i];
  }
  sort(a,a+n);
  int k=a[0];
  //cout<<k<<endl;
  //for(i=0;i<n;i++) cout<<a[i]<<' ';
  int p=0;
  while(k<=a[n-1])
  {
      int s=0;
      for(i=0;i<n;i++)
      {int m=abs(a[i]-k);
      //cout<<m<<' '<<s<<endl;
          s=s+(m*m);
      }
        k++;
      b[p++]=s;
  }
 // for(i=0;i<p;i++) cout<<b[i]<<' ';
  sort(b,b+p);
  cout<<b[0]<<endl;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long l, r;
long long minResult = INT64_MAX;

int main(int argc, char *argv[])
{
    cin >> l >> r;
    long long terminal = min(r, l + 2019);
    for (long long i = l; i < terminal; ++i)
    {
        for (long long j = l; j <= terminal; ++j)
        {
            if (i != j)
            {
                minResult = min((i * j) % 2019, minResult);
            }
        }
    }
    cout << minResult << endl;
}

Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;
use superslice::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;

#[fastout]
fn main() {
    input!{
        s: Chars,
    }

    if s[0] == s[1] || s[1] == s[2] || s[2] == s[0]  {
        println!("No");
    } else {
        println!("Yes");
    }
    
}


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

ll dp[100001];

int main()
{
    ll n,k;
    cin>>n>>k;
    ll a[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(ll i=2;i<n;i++)
    {
        ll x=LONG_MAX;
        for(ll j=i-1;j>=max((ll)0,i-k);j--)
        {
            x=min(x,(dp[j]+abs(a[j]-a[i])));
        }
        dp[i]=x;
    }
    cout<<dp[n-1]<<endl;

	return 0;
}

Measured memory_bytes: 5140
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
    ll n,k;
    cin >> n >> k;
    vector<pair<ll,ll>> move(k);
    for(int i = 0;i < k;i++)cin >> move[i].first >> move[i].second;
    vector<ll> sum(k,0);
    vector<ll> dp(n,0);
    dp[0] = 1;
    for(int i = 1;i < n;i++){
        for(int j = 0;j < k;j++){
            ll l = move[j].first;
            ll r = move[j].second;
            if(i - r >= 1)sum[j] = sum[j] - dp[i - r - 1] + dp[i - l];
            else if(i - l >= 0)sum[j] += dp[i - l];
          //cout << i << " "  << j << " " << sum[j] << endl;
        }
        for(int j = 0;j < k;j++){
          dp[i] += sum[j],dp[i] %= 998244353;
          //if(i == 2)cout << j << " " << sum[j] << endl;
        }
      //cout << dp[i] << endl;
    }
    cout << dp[n - 1] << endl;
}

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


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N+2);
    A[0] = 0; A[N+1] = 0;
    for(int i=1;i<=N;i++) cin >> A[i];
    ll sum = 0;
    for(int i=1;i<=N+1;++i) sum += abs(A[i] - A[i-1]);
    for(int i=1;i<N+1;++i) {
        ll res = sum + abs(A[i+1]-A[i-1]) - abs(A[i]-A[i-1]) - abs(A[i+1]-A[i]);
        cout << res << endl;
    }
    
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(x)    (x).begin(),(x).end()
typedef long long ll;
const int MOD = (int)1e9 + 7;

int main(){
  int h,w;
  cin >>h>>w;
  int x,y;
  cin>>x>>y;
  cout<<(h-x)*(w-y)<<endl;
}



Measured memory_bytes: 256
n = int(raw_input())
l = map(int, raw_input().split())
l = list(set(l))

while True:
    if len(l)==1:
        print(l[0])
        break
    else:
        ml = min(l)
        l = [i % ml for i in l]
        l.append(ml)
        l = filter(lambda x: x > 0, l)
        l = list(set(l))
        if len(l)==1:
            print(l[0])
            break
        ml = min(l)
        l = [i - ml for i in l]
        l.append(ml)
        l = filter(lambda x: x > 0, l)
        l = list(set(l))

Measured memory_bytes: 12624
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;
//using System.Numerics;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    Random rnd = new Random();
    Stopwatch sw = new Stopwatch();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;
    readonly string alfa = "abcdefghijklmnopqrstuvwxyz";
    readonly string ALFA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    int N;
    void solve()
    {
        N = cin.nextint;
        var P = cin.scanint.Select(i => i - 1).ToArray();
        int cnt = 0;
        for (int i = 0; i < N; i++)
        {
            if (P[i] == i)
            {
                if (i == N - 1)
                {
                    var t = P[i];
                    P[i] = P[i - 1];
                    P[i - 1] = t;
                    cnt++;
                }
                else
                {
                    var t = P[i];
                    P[i] = P[i + 1];
                    P[i + 1] = t;
                    cnt++;
                }
          
            }
        }
        WriteLine(cnt);
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 20572
n,weight = map(int, input().split())
wv=[list(map(int,input().split())) for i in range(n)]
w1=wv[0][0]

from collections import defaultdict
vals = defaultdict(list)
for tmp in wv:
    w,v=tmp
    vals[w-w1].append(v)

v1=sorted(vals[0],reverse=True)
v2=sorted(vals[1],reverse=True)
v3=sorted(vals[2],reverse=True)
v4=sorted(vals[3],reverse=True)

ans=-1
for num1 in range(len(v1)+1):
    for num2 in range(len(v2)+1):
        for num3 in range(len(v3)+1):
            for num4 in range(len(v4)+1):
                sumw = num1*w1 + num2*(w1+1) + num3*(w1+2) + num4*(w1+3)
                if sumw <=weight:
                    sm = sum(v1[:num1]) + sum(v2[:num2]) +  sum(v3[:num3]) +  sum(v4[:num4])
                    ans=max(ans,sm)
print(ans)

Measured memory_bytes: 56152
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <cstring>
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <numeric>
#include <float.h>
#include <math.h>
#include <sstream>
#include <iterator>
using namespace std;
// repマクロの定義
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// allマクロの定義
#define all(v) v.begin(), v.end()
const  long long INF = 1LL << 60;
typedef unsigned long long 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;
}



int ctoi(char c) {
 	switch (c) {
		case '0': return 0;
		case '1': return 1;
		case '2': return 2;
		case '3': return 3;
		case '4': return 4;
		case '5': return 5;
		case '6': return 6;
		case '7': return 7;
		case '8': return 8;
		case '9': return 9;
		default: return 0;
	}
}

bool is_prime(const unsigned n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: // fall-through
        case 3: return true;
    } // n > 3 が保証された

    if(n % 2 == 0 || n % 3 == 0) return false;
    // n は 2 と 3 のいずれの倍数でもないことが保証された
    // これより n は (6の倍数)-1 か (6の倍数)+1 である

    // 6の倍数前後の数を使って試し割りをする
    for(unsigned i = 5; i * i <= n; i += 6) {
        if(n % i     == 0) return false; // (6の倍数)-1
        if(n % (i+2) == 0) return false; // (6の倍数)+1
    }

    return true;
}

map<ll,ll> mp;

auto findFactors(ll num){
	
    ll i;
    while (num % 2 == 0){ // 偶数の素数は2のみ
        if(mp.count(2)){
			mp[2] = mp[2] + 1;
		}
		else{
			mp[2] = 1;
		}
        num /= 2;
    }
    for (i = 3; i <= num; i++){ // 他の素数で割っていく
        while (num % i == 0){
			if(mp.count(i)){
			mp[i] = mp[i] + 1;
		}
		else{
			mp[i] = 1;
		}
            num /= i;
        }
    }
    return 0;
}
ll kaizyou(ll n){
    if(n == 1){
        return 1;
    }
    else{
        return (n * kaizyou(n-1)) % 1000000007;
    }
}

int main(){ 
    ll A,B,C; cin >> A >> B >> C;
    ll ans;
    if(A + B >= C ){
        ans = B + C;
    }
    else{
        ans = A + 2 * B + 1;
    }
    cout << ans << endl;
    }

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

using namespace std;




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

	int N;
	cin >> N;

	vector<int> v(N);

	int mx = 0;

	for (int i = 0; i < N; ++i) {
		cin >> v[i];
		mx = max(mx, v[i]);
	}

	long long ans = 0x3f3f3f3f;

	for (int m = 1; m <= mx; ++m) {
		long long cur = 0;
		for(int x : v) {
			cur += abs(x - m) * abs(x - m);
		}
		ans = min(ans, cur);
	}
	
	cout << ans << '\n';



	return 0;
}

Measured memory_bytes: 256
N,X=map(int,input().split())
L=[1]
P=[1]
for i in range(N):
    L.append(L[i]*2+3)
    P.append(P[i]*2+1)

def dp(cur,X,ans):
    if cur==0:
        if X==0:
            return ans
        else:
            return ans+1
    elif X==0:
        return ans
    elif X>0 and X<=1+L[cur-1]:
        return dp(cur-1,X-1,ans)
    elif X==2+L[cur-1]:
        return ans+P[cur-1]+1
    elif X>2+L[cur-1] and X<L[cur]:
        return dp(cur-1,X-L[cur-1]-2,ans+P[cur-1]+1)
    else:
        return ans+P[cur]
        
print(dp(N,X,0))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
   #define PP pair<int,pair<int,int>>
const int MAX = 1000001;
const int MOD =1000000007;
const int INV2 = (MOD+1)/2;



     signed main(){
   int n,k,d,a,ans=0;
   cin>>n>>k;
   int x[n]={};
   for(int i=0;i<k;i++){
     cin>>d;
     for(int j=0;j<d;j++){
       cin>>a;a--;x[a]++;
     }
   }
   for(int i=0;i<n;i++)if(x[i]==0)ans++;
   cout<<ans<<endl;

        





}


        


Measured memory_bytes: 3624
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] list = new int[m];

        for (int i = 0; i < m ; i++) {
            list[i] = sc.nextInt();
        }

        Arrays.sort(list);

        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());

        int sum = 0;

        for (int i = 0; i < m - 1; i++) {
            int gap = Math.abs(list[i + 1] - list[i]);
            queue.add(gap);
            sum += gap;
        }

        for (int i = 0; i < n - 1 ; i++) {
            if (queue.size() == 0) {
                break;
            }
            sum -= queue.poll();
        }

        System.out.println(sum);
    }
}

Measured memory_bytes: 50416
import sys

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

A=["."*(W+2)]
T=0
for _ in range(H):
    G=input()
    A.append("."+G+".")
    T+=G.count("#")
    
A.append("."*(W+2))

x,y=1,1
U=1
while x<W or y<H:
    p=(A[y+1][x]=="#")
    q=(A[y][x+1]=="#")

    if p^q:
        if p:
            y=y+1
        else:
            x=x+1
        U+=1
    else:
        print("Impossible")
        sys.exit()

if T==U:
    print("Possible")
else:
    print("Impossible")


Measured memory_bytes: 62060
#include <bits/stdc++.h>
using namespace std;
#define MD 1000000007
typedef long long int ll;
typedef pair<ll, ll> P;
template <typename T>
std::string tostr(const T &t){std::ostringstream os;os << t;return os.str();}
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<<min(b/a,c)<<endl;
    return 0;
}

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


import math

# def equation(a, b, c):
#     D = (b**2 - 4*a*c) ** (1/2)
#     x_1 = (-b + D) / (2 * a)
#     x_2 = (-b - D) / (2 * a)

#     return x_1, x_2



def main():
    n = int(input())

    ans = [0]*(n+1)

    for x in range(1, int(math.sqrt(n))):
        for y in range(1, int(math.sqrt(n))):
            for z in range(1, int(math.sqrt(n))):

                e = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if e >= 1 and e <= n:
                    ans[int(e)] += 1

    for i in range(len(ans)-1):
        print(ans[i+1])




                # x_1, x_2 = equation(1, y+z, y**2 + y*z + z**2 - n)

                # if isinstance(x_1, float):
                #     x_1 = round(x_1, 5)
                #     if x_1.is_integer() == True and x_1 >= 1:
                #         cnt += 1

                # if isinstance(x_2, float):
                #     x_2 = round(x_2, 5)
                #     if x_2.is_integer() == True and x_2 >= 1:
                #         cnt += 1

        # print(cnt)




if __name__ == '__main__':
    main()


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

int main() {
	int X;
	cin >> X;
	int C500 = X / 500;
	X %= 500;
	int C5 = X / 5;
	X %= 5;
	int U = 1000 * C500 + 5 * C5;
	cout << U << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
	string S;
	int length=0;
	int nBtoW=0,nWtoB=0;
	char lastSpell=0;
	int i;
	cin>>S;
	length=S.size();
	lastSpell=S[0];

	for(i=0; i<length; i++){
		if(S[i] != lastSpell){
			if(lastSpell=='W'){
				nWtoB++;
			}else{
				nBtoW++;
			}
			lastSpell=S[i];
		}
	}
	//cout<<nBtoW<<" "<<nWtoB<<endl;

	cout<<nBtoW + nWtoB <<endl;

	
	return 0;
}

Measured memory_bytes: 512
// -*- mode:c++; coding:utf-8; c-basic-offset:2; -*-
// ALDS1_12_B: Single Source Shortest Path I

#include <algorithm>
#include <cstdio>

using uint = unsigned int;

class Graph {
  const uint n_;
  uint* const g_;
  const uint INFINIT;
  
public:

  Graph(uint n) : n_(n), g_(new uint[(n_*n_)]), INFINIT(100000*(n_-1)+1) {
    std::fill_n(g_, (n_*n_), INFINIT);
  }

  ~Graph() { delete[] g_; }
  
  uint* operator [](uint i) const { return g_+(n_*i); }

  void dijkstra(uint* dist)
  {
    std::fill_n(dist, n_, INFINIT);
    bool visited[n_];
    std::fill_n(visited, n_, false);
    auto i = 0u; // 0-start
    visited[i] = true;
    dist[i] = 0u;
    for (auto n = 0u; n < n_-1; ++n) {
      auto cur_min = INFINIT;
      auto es = (*this)[i];
      auto base_dist = dist[i];
      for (auto j = 0u; j < n_; ++j) {
        if (visited[j]) continue;
        dist[j] = std::min(dist[j], base_dist+es[j]);
        if (cur_min > dist[j]) {
          cur_min = dist[j];
          i = j;
        }
      }
      visited[i] = true;
    }
  }
};

int main()
{
  uint n;
  std::scanf("%u", &n);

  Graph g(n);

  uint u, k, c, v;
  for (auto i = 0u; i < n; ++i) {
    std::scanf("%u %u", &u, &k);
    for (auto j = 0u; j < k; ++j) {
      std::scanf("%u %u", &c, &v);
      g[u][c] = v;
    }
  }

  uint dist[n];
  g.dijkstra(dist);
  for (auto i = 0u; i < n; ++i) {
    std::printf("%u %u\n", i, dist[i]);
  }
}

// eof

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

ll dfs(int K,const vector<vector<int>>&graph, int now,int from){

  int can_use_color_num;
  if(from == -1)can_use_color_num = K-1;
  else can_use_color_num = K-2;

  if(K<graph[now].size())return 0;
  else{
    ll case_num=1;
    for(auto e : graph[now]){
      if(e==from)continue;
      case_num*=can_use_color_num;
      can_use_color_num--;
      case_num%=mod;
    }
    for(auto e : graph[now]){
      if(e==from)continue;
      case_num*=dfs(K,graph,e,now);
      case_num%=mod;
    }
    return case_num;
  }
}

int main(){
  int N,K;
  cin>>N>>K;
  vector<vector<int>>graph(N);
  for (int i = 0; i < N - 1; ++i) {
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  ll ans = K*dfs(K,graph,0,-1);
  ans %= mod;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11520
while True:
    n = int(input())
    if n == 0:
        break

    s = list(map(int, input().split()))
    m = sum(s) / n
    v = 0
    for si in s:
        v += (si - m) ** 2
    ans = (v / n) ** 0.5
    print("{:.5f}".format(ans))


Measured memory_bytes: 5664
#include<stdio.h>
int main(void){
	double a,b,c,d,e,f,x,y;
	while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)!=EOF){
		y=(c*d-f*a)/(b*d-e*a);
		x=(c-b*y)/a;
		printf("%.3f %.3f\n",x,y);
	}
	return 0;
}

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

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
#define test cout<<"test"<<endl;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
const ll zero=0;
using P = pair<ll, ll>;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  ll n;cin>>n;
  vector<ll>a(n);
  for(i=0;i<n;i++)cin>>a[i];
  ll sumbuf=0;
  vector<ll>b(n);
  for(i=0;i<n;i++){
    sumbuf+=a[i];
  }
  b[0]=a[0]-a[n-1];
  for(i=1;i<n;i++)b[i]=a[i]-a[i-1];
  if(sumbuf%(n*(n+1)/2)!=0)judge=false;
  else{
    ll numbuf=sumbuf/((n*(n+1))/2);
    ll countbuf=0;
    //cout<<sumbuf spa numbuf<<endl;
    for(i=0;i<n;i++){
      //cout<<numbuf-b[i] spa b[i]<<endl;
      if((numbuf-b[i])<-1||(numbuf-b[i])%n!=0){
        judge=false;break;
      }
      else{
        countbuf+=(numbuf-b[i])/n;
      }
    }
    if(countbuf!=numbuf)judge=false;
  }
  ans2(judge);
  return 0;
}

Measured memory_bytes: 1792
def maxHeapify(A, i):
    l = 2 * i
    r = 2 * i + 1
    largest = i
    if l < len(A) and A[l] > A[largest]:
        largest = l
    if r < len(A) and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)


def buildMaxHeap(A):
    for i in reversed(range(1, H // 2 + 1)):
        maxHeapify(A, i)


H = int(input())
A = list(map(int, input().split()))
A.insert(0, None)
buildMaxHeap(A)
print(' ' + ' '.join(map(str, A[1:])))



Measured memory_bytes: 64204
#include<stdio.h>

int main(){
	int a,b,c;
	
  	scanf("%d",&a);

  	scanf("%d",&b);
  	
	
 	if(b % a == 0){
		c = a + b;
    }else{
		c = b - a;
    }
  
  	printf("%d",c);
	return 0;
  
}



Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
using namespace std;

typedef long long i64;
const int MAX_N = 200005;

char S[MAX_N];
int N, cnt[26];
deque<int> pos[26];

class Fenwick {
public:
  int sum[MAX_N];
  void update(int x, int v) {
    for (; x <= N; x += x &-x)
      sum[x] += v;
  }
  int ask(int x) {
    int res = 0;
    for (; x; x -= x & -x)
      res += sum[x];
    return res;
  }
} tr;

int main() {
  scanf("%s", S + 1);
  N = strlen(S + 1);
  for (int i = 1; i <= N; ++i) {
    cnt[S[i] - 'a'] ^= 1;
    pos[S[i] - 'a'].push_back(i);
  }
  
  int num = 0;
  for (int i = 0; i < 26; ++i)
    if (cnt[i] & 1)
      num++;
  if (num > 1) {
    puts("-1");
    return 0;
  }

  i64 result = 0;
  for (int i = 1; i <= N / 2; ++i) {
    int mn = 1000000000, mnid = 0;
    for (int j = 0; j < 26; ++j)
      if (pos[j].size() >= 2) {
	int p1 = pos[j].front() + tr.ask(pos[j].front());
	int p2 = pos[j].back() + tr.ask(pos[j].back());
	int l = p1 - i + N - i + 1 - p2;
	if (l < mn) mn = l, mnid = j;
      }
    result += mn;
    //move(pos[mnid].front(), i);
    //move(pos[mnid].back(), N - i + 1);
    tr.update(1, 1), tr.update(pos[mnid].front(), -1);
    tr.update(pos[mnid].back(), -1);
    pos[mnid].pop_front(), pos[mnid].pop_back();
  }

  printf("%lld\n", result);
  return 0;
}


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

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

using namespace std;

typedef long long LL;

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

    int A, B;
    cin >> A >> B;

    if (A == B) {
        cout << 2 * A << endl;
    } else {
        cout << 2 * max(A, B) - 1 << endl;
    }

}


Measured memory_bytes: 256
// ARC086
// D - Non-decreasing

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_N = 50;
const int MAX_A = 1e6;

int N;
int a[MAX_N];

int main() {
    cin >> N;
    int min_a = MAX_A, max_a = -MAX_A;
    int min_i, max_i;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        if (a[i] < min_a) {
            min_a = a[i];
            min_i = i;
        }
        if (a[i] > max_a) {
            max_a = a[i];
            max_i = i;
        }
    }

    bool inv = abs(min_a) > abs(max_a);
    vector<pii> ans;
    for (int i = 0; i < N; i++) {
        if (inv && a[i] > 0) {
            ans.push_back(pii(min_i + 1, i + 1));
        } else if (!inv && a[i] < 0) {
            ans.push_back(pii(max_i + 1, i + 1));
        }
    }

    if (inv) {
        for (int i = N - 1; i > 0; i--) {
            ans.push_back(pii(i + 1, i));
        }
    } else {
        for (int i = 1; i < N; i++) {
            ans.push_back(pii(i, i + 1));
        }
    }

    cout << ans.size() << endl;
    for (int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i].first << " " << ans[i].second << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#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 A, B, K;
    cin >> A >> B >> K;
    if (K <= A) {
        A -= K;
    } else if (K <= A + B) {
        B -= K - A;
        A = 0;
    } else {
        A = 0;
        B = 0;
    }
    cout << A << " " << B << endl;
}


Measured memory_bytes: 256
a, b = input().split()
a = int(a)
b = int(b)

c=1
if a*b*c%2==0:
    c=2
    if a*b*c%2==0:
        c=3
        if a*b*c%2==0:
            print("No")
        else:
            print("Yes")   
    else:
        print("Yes")        
else:
    print("Yes")

Measured memory_bytes: 3060
class Node():
    def __init__(self, id, key, parent, left, right):
        self.id = id
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
    def show(self):
        print 'node %d: key = %d,' % (self.id, self.key),
        if self.parent:
            print 'parent key = %d,' % self.parent, 
        if self.left:
            print 'left key = %d,' % self.left,
        if self.right:
            print 'right key = %d,' % self.right,
        print ''

def calcParent(key):
    if key == 1:
        return None
    else:
        return data[int(key/2) - 1]

def calcLeft(key, flag=0):
    if flag == 1:
        return 2 * key
    if 2 * key < n + 1:
        return data[2 * key - 1]
    return None

def calcRight(key, flag=0):
    if flag == 1:
        return 2 * key + 1
    if 2 * key < n:
        return data[2 * key]
    return None

def maxHeapify(T, i):
    val_i, val_l, val_r = T[i].key, None, None
    if T[i].left:
        val_l = T[i*2].key
    if T[i].right:
        val_r = T[i*2+1].key
    if val_l and val_l > val_i:
        largest = val_l
    else:
        largest = val_i
    if val_r and val_r > largest:
        largest = val_r
    if largest != val_i:
        T[i].key = largest
        if T[i].parent:
            if T[int(i/2)].left == val_i:
                T[int(i/2)].left = largest
            else:
                T[int(i/2)].right = largest
        if largest == val_l:
            T[i*2].key = val_i
            T[i*2].parent = largest
            T[i].left = val_i
            T = maxHeapify(T, i*2)
        else:
            T[i*2+1].key = val_i
            T[i*2+1].parent = largest
            T[i].right = val_i
            T = maxHeapify(T, i*2+1)
    return T
        
n = int(raw_input())
data = map(int, raw_input().split())
T = {}
for i in range(n):
    this_id = i + 1
    T[this_id] = Node(i+1, data[i], calcParent(this_id), calcLeft(this_id), calcRight(this_id))
for i in range(int(n/2), 0, -1):
    T = maxHeapify(T, i)
    
print '',
for i in T.keys():
    print  T[i].key,

Measured memory_bytes: 252336
#include<stdio.h>
#include<stdlib.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

typedef struct indexVal{
  int64 val;
  int index;
} node;

typedef struct deque{
  node *a;
  int front;
  int last;
  int len;
} deque;

deque* newDeque(int len){
  deque *d=(deque *)calloc(1,sizeof(deque));
  d->a=(node *)calloc(len,sizeof(node));
  d->front=d->last=0;
  d->len=len;
  return d;
}

void push_back(deque *d,node v){
  d->a[d->last++]=v;
  d->last%=d->len;
}

node pop_front(deque *d){
  node t=d->a[d->front++];
  d->front%=d->len;
  return t;
}

node pop_back(deque *d){
  d->last=(d->last+d->len-1)%d->len;
  return d->a[d->last];
}

node get_front(deque *d){
  return d->a[d->front];
}

node get_back(deque *d){
  return d->a[(d->last+d->len-1)%d->len];
}

int isEmpty(deque *d){
  return d->front==d->last;
}

void clear(deque *d){
  d->front=d->last=0;
}

#define POS(i,j) ((i)*(k+1)+(j))

void run(void){
  int n,m,k;
  scanf("%d%d%d",&n,&m,&k);
  int *a=(int *)calloc(n+1,sizeof(int));
  int i;
  for(i=1;i<=n;i++) scanf("%d",a+i);
  int64 *dp=(int64 *)calloc(n+1,sizeof(int64));
  deque *deq=newDeque(m+1);
  for(i=1;i<=k;i++){
    clear(deq);
    push_back(deq,(node){dp[i-1],i-1});
    for(int j=i;j<=n;j++){
      node t=get_front(deq);
      while(t.index<j-m){
	pop_front(deq);
	t=get_front(deq);
      }
      int64 local=(int64)i*a[j]+t.val;
      while(!isEmpty(deq)){
	t=get_back(deq);
	if(t.val>dp[j]) break;
	pop_back(deq);
      }
      push_back(deq,(node){dp[j],j});
      dp[j]=local;
    }
  }
  int64 ans=0;
  for(i=k;i<=n;i++) ans=MAX(ans,dp[i]);
  printf("%lld\n",ans);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 1408
import java.util.*;

public class Main {

    static <T extends Comparable<? super T>> boolean nextPermutation(T[] sequence) {
        int first = getFirst(sequence);
        if (first == -1) return false;
        int toSwap = sequence.length - 1;
        while (sequence[first].compareTo(sequence[toSwap]) >= 0) --toSwap;
        swap(sequence, first++, toSwap);
        toSwap = sequence.length - 1;
        while (first < toSwap) swap(sequence, first++, toSwap--);
        return true;
    }

    static <T extends Comparable<? super T>> int getFirst(T[] sequence) {
        for (int i = sequence.length - 2; i >= 0; --i)
            if (sequence[i].compareTo(sequence[i + 1]) < 0) return i;
        return -1;
    }

    static <T extends Comparable<? super T>> void swap(T[] sequence, int i, int j) {
        T tmp = sequence[i];
        sequence[i] = sequence[j];
        sequence[j] = tmp;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] matrix = new int[N][N];
        for (int i = 0; i < N; ++i) Arrays.fill(matrix[i], 0);
        for (int i = 0; i < M; ++i) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            matrix[a][b] = 1;
            matrix[b][a] = 1;
        }

        Integer[] arr = new Integer[N];
        for (int i = 0; i < N; ++i) arr[i] = i;

        int cnt = 0;
        do {
            if (arr[0] != 0) break;
            boolean flag = true;
            for (int i = 0; i < N-1; ++i) {
                if (matrix[arr[i]][arr[i+1]] == 0) flag = false;
            }
            if (flag) ++cnt;
        } while (nextPermutation(arr));

        System.out.println(cnt);
    }
}

Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		int[] left = new int[N];
		int[] right = new int[N];
		for(int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		sc.close();
		// System.out.println("--------");
		// 左からのMAXを保持
		left[0] = A[0];
		// System.out.print(left[0] + " ");
		for(int i = 1; i < N; i++) {
			left[i] = Math.max(left[i - 1], A[i]);
			// System.out.print(left[i] + " ");
		}
		// System.out.println("");
		// 右からのMAXを保持
		right[N - 1] = A[N - 1];
		// System.out.print(right[N - 1] + " ");
		for(int i = N - 2; i >= 0; i--) {
			right[i] = Math.max(right[i + 1], A[i]);
			// System.out.print(right[i] + " ");
		}
		// System.out.println("\n--------");
		// 結果出力
		for(int i = 0; i < N; i++) {
			int l = i == 0 ? 0 : left[i - 1];
			int r = i == N - 1 ? 0 : right[i + 1];
			System.out.println(Math.max(l, r));
		}
	}
}	


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

int main(){
  ll N,ans=0;
  cin >> N;
  vector<int> A(N),B(N);
  rep(i,N) {
    cin >> A[i];
    B[i] = A[i];
  }
  rep(i,N-1) {
    if(B[i]>B[i+1]){
      ans += B[i] - B[i+1];
      B[i+1]=B[i];
    }
  }
  cout << ans << endl;
  return 0; 
}

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;

int main() {
    int h,w,n;
    cin>>h>>w>>n;

    int m=max(h,w);
    cout<<(n+m-1)/m<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef  long double ld;
#define inc(i,a,b)  for(long long int i=a;i<=b;i++)
#define dec(i,a,b)  for(long long int i=a;i>=b;i--)
#define fast   ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define lv  vector<ll>
#define cv  vector<char>
#define dv  vector<ld>
#define rall(c)  (c).rbegin(),(c).rend()
#define lpr pair<ll,ll>
#define mp make_pair
#define input(c) ll c;cin>>c;
#define lmap map<ll,ll>
#define vinp(a,n) inc(i,1,n){ input(k); a.pb(k); }
#define LIM 1000000007
#define F first
#define S second
#define fr(n,i) inc(i,0,n-1)
#define fri(n,a) inc(i,0,n-1){ cin>>a[i]; }
void solve()
{
	ll n;
	cin>>n;
	ll A[n];
	fri(n,A);
	sort(A,A+n); 
	ll count = 0; 
	for( ll i = n-1; i >= 1; i--){ 
		ll l = 0, r = i-1; 
		while( l < r){ 
			if( A[l] + A[r] > A[i]){ 
        	count += r - l ; 
			r--; 
			} 
			else
			l++; 
		} 
	} 
	cout<<count; 
} 	 
int main()
{
	fast;
	ll t=1;
    //cin>>t;
	while(t--)
    solve();
}


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

using namespace std;

int CountPath(const vector<vector<int>> &g) {
    const int s = 0;
    const int n = g.size();
    int cnt = 0;
    vector<int> idx(n - 1);

    for (int i = 0; i < n - 1; ++i)
        idx[i] = i + 1;

    do {
        bool can_reach = true;
        int cur = s;

        for (int i = 0; i < n - 1; ++i) {
            bool can_nxt = false;
            for (auto u : g[cur])
                if (u == idx[i]) {
                    can_nxt = true;
                    break;
                }

            if (!can_nxt) {
                can_reach = false;
                break;
            }

            cur = idx[i];
        }

        if (can_reach) ++cnt;

    } while (next_permutation(idx.begin(), idx.end()));

    return cnt;
}

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

    int n, m, a, b;

    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        g[a - 1].emplace_back(b - 1);
        g[b - 1].emplace_back(a - 1);
    }

    cout << CountPath(g) << endl;

    return 0;
}


Measured memory_bytes: 256