akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

//****************************************************                
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll> 
#define vpll vector<pll>
#define all(X) X.begin(),X.end()
#define endl "\n" //comment it for interactive questions
#define trace1(a) cerr << #a << ": " << a << endl;
#define trace2(a,b) cerr << #a << ": " << a << " " << #b << ": " << b << endl;
#define trace3(a,b,c) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << endl;
#define trace4(a,b,c,d) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << #d << ": " << d << endl;
#define OC   
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
        //*******************************************************
//Some Functions

const ll MOD = 998244353; //change it for other mods

ll powmod(ll a,ll b)
{
   ll res = 1;
   while(b > 0) {
      if(b & 1) res = (res * a) % MOD;
      a = (a*a)%MOD;
      b = b >> 1; 
  }
  return res % MOD;
}
vll fact(300010, 1);

ll nck(ll n, ll k) {
	if(n < k) {
		return 0;
	}
	ll x1 = fact[n];
	ll x2 = powmod(fact[k], MOD-2);
	ll x3 = powmod(fact[n-k], MOD-2);
	ll yy = (x2*x3)%MOD;
	return (x1*yy)%MOD;
}

void solve(ll testnum)
{
    ll n,m,k;
    cin >> n >> m >> k;
    fact[0] = 1;
    for(ll i=1;i<=n;i++) {
    	fact[i] = (fact[i-1]*i)%MOD;
    }
    ll ans = (m*powmod(m-1, n-1))%MOD;
    // cout << ans << "\n";
    for(ll i=1;i<=k;i++) {
    	ll cnt = 0;
    	cnt = nck(n-1, i);
    	// cout << i << " " << cnt << "\n";
    	cnt%=MOD;
    	ll ans2 = (m*powmod(m-1, n-1-i))%MOD;
    	ll ans3 = (cnt*ans2)%MOD;
    	ans += ans3;
    	ans%=MOD;
    }
    cout << ans << "\n";
}

int main()
{
    FAST_IO;
    #ifdef STIO 
      freopen("input.txt" , "r", stdin);
      freopen("output.txt" , "w", stdout);
    #endif
    ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++) {
        solve(i);
    }
}

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int MAXN=101010;
int N,K,h[MAXN],dp[MAXN];

int main(){
//#ifdef Javier
//    freopen(".in", "r", stdin);
//#endif // Javier

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

    cin>>N>>K;
    for(int i=1;i<=N;i++)
        cin>>h[i];

    fill(dp,dp+N+1,1e9);
    dp[1]=0;
    dp[2]=abs(h[2]-h[1]);

    for(int i=3;i<=N;i++)
    {
        for(int j=1;j<=K && i-j>=1 ;j++)
        {
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
        }
    }

    cout<<dp[N];
    return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
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 (a>b) { a=b; return 1; } return 0; }

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

	string s; cin >> s;
    int cntn = 0;
    int cnts = 0;
    int cnte = 0;
    int cntw = 0;
    rep(i,s.size()) {
        if(s[i] == 'N') cntn++;
        if(s[i] == 'S') cnts++;
        if(s[i] == 'W') cntw++;
        if(s[i] == 'E') cnte++;
    }
    bool check = true;
    if((cntn == 0 and cnts > 0) or (cnts == 0 and cntn > 0)) check = false;
    if((cntw == 0 and cnte > 0) or (cnte == 0 and cntw > 0)) check = false;
    if(check) {cout << "Yes" << endl; return 0;}
    else {cout << "No" << endl; return 0;}
}

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

using namespace std;

long long n;

long long gcd(long long x,long long y){
    return (y == 0)?x:gcd(y,x%y);
}

vector<pair<long long,long long> > soin(long long x){
    vector<pair<long long,long long> > vp;
    long long i,j;
    for(i = 2;i*i <= x;i++){
        if(x % i == 0){
            for(j = 0;x % i == 0;j++) x /= i;
            vp.push_back(make_pair(i,j));
        }
    }
    if(x > 1) vp.push_back(make_pair(x,1));
    return vp;
}

void solve(){
    long long a,b;
    int i,j;
    cin >> a >> b;
    vector<pair<long long,long long> > sa = soin(a);
    vector<pair<long long,long long> > sb = soin(b);
    int ans = 1;
    for(i = 0,j = 0;i < sa.size() && j < sb.size();){
        if(sa[i].first == sb[j].first){
            ans++;
            i++;
            j++;
        }
        else if(sa[i].first > sb[j].first){
            j++;
        }
        else{
            i++;
        }
    }
    cout << ans << endl;
}

int main(){
    solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
#define int long long
using namespace std;
int n,k,A[li],cev,fac[li];
inline int mul(int x,int y){
	return (x%md)*(y%md)%md;
}
inline int add(int x,int y){
	if(x+y>=md) return x+y-md;
	return x+y;
}
int fp(int a,int b){
	if(b==0) return 1;
	if(b==1) return a%md;
	int t=fp(a,b/2);
	t=mul(t,t);
	if(b%2==1) t=mul(t,a);
	return t;
}
int cmb(int nn,int kk){
	if(nn<kk) return 0;
	int hop=mul(fac[kk],fac[nn-kk]);
	return mul(fac[nn],fp(hop,md-2));
}
main(){
	scanf("%lld %lld",&n,&k);
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
	for(int i=1;i<=n;i++){
		scanf("%lld",&A[i]);
	}
	sort(A+1,A+n+1);
	for(int i=1;i<=n;i++){
		int kucuk=i-1;
		int buyuk=n-i;
		cev=add(cev,mul(cmb(kucuk,k-1),A[i]));
		cev=add(cev,md-mul(cmb(buyuk,k-1),A[i]));
	}
	printf("%lld\n",cev);
	return 0;
}




Measured memory_bytes: 1792
n, k = map(int, input().split())
hs = list(map(int, input().split()))

results = list()

results.append(0)

for i in range(1, n):
    score = float('INF')
    for j in range(1, min(k+1, i + 1)):
        score = min(score, results[i-j] + abs(hs[i-j] - hs[i]))
    results.append(score)

print(results[n-1])


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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i ++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i --)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {T a; K b;};

int main( void ){
	initialize();
	ll N;
	cin >> N;
	rep(i,0,N){
		int input; cin >> input;
		if (input %2 == 0 &&input %3 != 0 && input %5 != 0){
			cout << "DENIED\n";
			return 0;
		}
	}
	cout << "APPROVED\n";
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
	// cin.tie( 0 );
	// ios::sync_with_stdio( false );
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[35]={0,1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main(){
	int n;
	cin>>n;
	cout<<a[n]<<endl;
	return 0;
}

Measured memory_bytes: 256
K, N = [int(v) for v in input().strip().split()]
A = [int(v) for v in input().strip().split()]

D = 0

for idx, a in enumerate(A):
    d = K + a - A[idx-1] if idx == 0 else a - A[idx-1]
    if D < d:
        D = d
print(K-D)

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

int main() {
	char b;
	cin >> b;

	if (b == 'A') {
		cout << 'T' << endl;
	}

	if (b == 'T') {
		cout << 'A' << endl;
	}

	if (b == 'C') {
		cout << 'G' << endl;
	}

	if (b == 'G') {
		cout << 'C' << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
ll LCM(ll a,ll b){return (a*b)/GCD(a,b);}
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main()
{
	int a, b;
	cin >> a >> b;
	cout << max(0, a-b*2) << endl;
}


Measured memory_bytes: 256
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

class SegmentTree{
    int N;
    long[] data;

    SegmentTree(int N){
        this.N=1;
        while(this.N<N)this.N*=2;
        data = new long[this.N*2-1];
        Arrays.fill(data,0);
    }

    //0-index
    void add(int index,long value){
        index += N-1;
        data[index] += value;
        while(index>0){
            index = (index-1)/2;
            data[index]+=value;
        }
    }

    private long getSum(int left,int right,int a,int b,int k){
        if(left<=a && b <= right)return data[k];
        if(b<=left || right <= a)return 0;
        return getSum(left,right,a,(a+b)/2,2*k+1) + getSum(left, right,(a+b)/2,b,2*k+2);
    }

    //[left,right)
    long getSum(int left, int right){
        return getSum(left, right,0,N,0);
    }
}

class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String s = scan.next();
        Deque<Integer>[] charIndexes = new ArrayDeque[26];
        for(int i=0;i<26;++i)charIndexes[i]=new ArrayDeque<>();
        for(int i=0;i<s.length();++i){
            charIndexes[s.charAt(i) - 'a'].add(i);
        }
        int odd = 0;
        for(int i=0;i<26;++i)if(charIndexes[i].size()%2==1)++odd;
        if(odd>1){
            System.out.println(-1);
            return;
        }
        //そのindex以降にあるやつで既に消えたやつは数えない
        //→segtreeで管理
        SegmentTree st = new SegmentTree(s.length());
        long ans=0;
        boolean oddFlag = false;
        for(int i=0;i<s.length();++i){
            int nextc = s.charAt(i)-'a';
            if(charIndexes[nextc].isEmpty() || charIndexes[nextc].getFirst() != i)continue;
            if(charIndexes[nextc].size()==1){
                oddFlag = true;
                continue;
            }
            int f = charIndexes[nextc].removeFirst();
            int l = charIndexes[nextc].removeLast();
            //lがs.length()-1　→0移動
            ans += (long)(s.length()-1)-l - st.getSum(l, s.length()) +(oddFlag ? 1:0);
            st.add(l,1);
        }
        System.out.println(ans);

    }
}

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

using namespace std;

#define _46_days ""

typedef long long ll;

int main() {
    ll a, b;
    cin >> a >> b;
    if ((a <= 0 && b >= 0) || !a || !b) {
        cout << "Zero";
        return 0;
    }
    else if (a > 0 && b > 0) {
        cout << "Positive";
        return 0;
    }
    else if (a < 0 && b < 0) {
        int x = max(abs(a), abs(b));
        int y = min(abs(a), abs(b));
        cout << ((x - y + 1) % 2 == 1 ? "Negative" : "Positive");
        return 0;
    }
    cout << "Zero";
}


Measured memory_bytes: 256
import scala.io.{StdIn => in}

object Main extends App {
  val S = in.readLine
  val N = S.toInt

  def dfsEnum(d:Int, n:Int):Int = {
    // d進 n個列挙
    val list = Array(7,5,3)
    val enum = Array.ofDim[Int](n)
    var ret = 0
  
    def evalute():Unit = {
      if(enum.distinct.size == 3 && enum.mkString.toInt <= N)
        ret += 1
    }
  
    def dfs(cnt:Int):Unit = {
      if(cnt == n) evalute
      else {
        for(i <- 0 until d) {
          enum(cnt) = list(i)
          dfs(cnt+1)
        }
      }
    }
  
    dfs(0)
    ret
  }

  val ans = if(N < 357) 0 else (1 to S.size).map(i => dfsEnum(3,i)).sum
  println(ans)
}

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

ll pow(ll x,ll y){
  if(y==0){
    return 1;
  }else if(y==1){
    return x%MOD;
  }else if(y%2==0){
    return pow(x,y/2)*pow(x,y/2)%MOD;
  }else{
    return x*pow(x,y-1)%MOD;
  }
}

int main(){
  vector<int> A(9,0);
  for(int i=0;i<9;i++){
    cin >> A[i];
  }
  vector<bool> T(9,false);
  int N;cin >> N;
  for(int i=0;i<N;i++){
    int b;cin >> b;
    for(int j=0;j<9;j++){
      if(b==A[j]){
        T[j] = true;
      }
    }
  }
  bool x = (T[0]&&T[1]&&T[2])||(T[3]&&T[4]&&T[5])||(T[6]&&T[7]&&T[8]);
  bool y = (T[0]&&T[3]&&T[6])||(T[1]&&T[4]&&T[7])||(T[2]&&T[5]&&T[8]);
  bool z = (T[0]&&T[4]&&T[8])||(T[2]&&T[4]&&T[6]);
  if(x||y||z){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int N, b, f, r, v, house[4][3][10];

    cin >> N;

    for(int i=0; i<4; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<10; k++)
                house[i][j][k] = 0;
        }
    }

    for(int i=0; i<N; i++){
        cin >> b >> f >> r >> v;
        house[b-1][f-1][r-1] += v;
    }

    for(int i=0; i<4; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<10; k++){
                cout << " " << house[i][j][k];
             }
            cout << endl;
        }
        if(i != 3)
            cout << "####################" << endl;
    }
}


Measured memory_bytes: 3112
ar = list(input())
b = 0
while True:
    count = 0
    for i in range(1,len(ar)-1):
        if ar[i-1] != ar[i+1]:
            count +=1
            del ar[i]
            b += 1
            break
    if count == 0:
        if b % 2 == 1:
            print("First")
        else:
            print("Second")
        break

Measured memory_bytes: 4084
#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 rep(i,n) FOR(i,0,n)
#define each(e,v) for(auto&& e:(v))
#define DEBUG(x) cout<<#x<<": "<<x<<endl
using namespace std;
using vint = vector<int>;
using vdouble = vector<double>;
using vstring = vector<string>;

int main() {
    set<int> s;
    rep(i, 3) {
        int a; cin >> a;
        s.insert(a);
    }
    cout << s.size() << endl;
    return 0;
}


Measured memory_bytes: 256
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N, K = sc.nextInt
  val Hs = Array(0) ++ Array.fill(N)(sc.nextInt) ++ Array(0)
  var dp = Array.fill(N + 2, N + 1)(1000000000000L)
  dp(0)(0) = 0
  for(i <- 0 to N + 1) {
    for(j <- 0 until i) {
      val p = i - j - 1
      for(s <- 0 to K - p) {
        val t = dp(j)(s) + (if(Hs(i) > Hs(j)) Hs(i) - Hs(j) else 0)
        if(dp(i)(s + p) > t) dp(i)(s + p) = t
      }
    }
  }
  println(dp(N + 1).min)
}

Measured memory_bytes: 31852
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	vector<int> a(n);
	int largest = -1;
	int idx = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (a[i] > largest) {
			largest = a[i];
			idx = i;
		}
	}

	int closest = largest / 2;
	int second_num = INT_MIN;
	int curr_closest = INT_MAX;
	for (int i = 0; i < n; ++i) {
		if (i == idx) {
			continue;
		}

		if (a[i] == closest) {
			cout << largest << " " << a[i] << "\n";
			return 0;
		}

		if (abs(a[i] - closest) < curr_closest) {
			second_num = a[i];
			curr_closest = abs(a[i] - closest);
		}
	}

	cout << largest << " " << second_num << "\n";

	return 0;

}

Measured memory_bytes: 640
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

#define INF 999999999
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int pr[100001];

void erato(){
	pr[0]=0;
	pr[1]=0;
	pr[2]=1;
	for(int i=3;i<=100000;i++){
		pr[i]=1;
		for(int j=2;j*j<=i;j++){
			if(i%j==0){
				pr[i]=0;
				break;
			}
		}
	}
}

int main(){
	long long int m, a, b, p, q;
	erato();
	while(1){
		cin >> m >> a >> b;
		if(!m)break;
		p=1;
		q=1;
		for(long long int i=2;i<=m;i++){
			for(long long int j=i;j*i<=m;j++){
				if(!pr[i]||!pr[j]) continue;
				if(i*j<=m&&a*j<=i*b&&i*j>p*q){
					p=i;
					q=j;
				}
			}
		}
		cout << p << " " << q << endl;
	}
	return 0;
}

Measured memory_bytes: 1544
#include<iostream>
//#include <bits/stdc++.h>
using namespace std;
#include<algorithm>
#include<map>
#include<vector>
#include <iomanip>
#include <set>
#include<cmath>
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define mp make_pair
void sp(double y,int x){cout<<fixed<<setprecision(x)<<y;}
int inf=1e9+10;
int const M=2e5+10;
int const M2=1e6+10;
int const M3=1e3+10;
int mod=1e9+7;
int sa(int x,int y){if(x%y==0)return x/y;return x/y+1;}
int binp(int x,int y){int ans=1;int t=x;while(y!=0){if(y%2==1){ans*=t;ans;}y/=2;t*=t;t;}return ans;}
int main(){
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
	int n;
	cin>>n;
	cout<<"ABC";
	cout<<n;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {	
	int t=1;
	//cin >> t;
	while (t--) {
	   
	    int n;
       cin>>n;
       int k;
       cin>>k;
       int*arr=new int[n];
       for(int i=0;i<n;i++)
       {
       	cin>>arr[i];
	   }
	    long long dp[100001];
	   for(int i=0;i<n;i++)
	   {
	   	dp[i]=INT_MAX;
	   }
	   dp[0]=0;
	   int l;
	   long long a;
	   for(int i=0;i<n;i++)
	   {
	   	  
	     for(int j=1;j<=k;j++)
	     {
	     	l=i+j;
	     	if(l<=n)
	   	{ 
	   	   	a=dp[i]+abs(arr[i]-arr[l]);
	   	   	 if(dp[l]>a)
	   	   	 {
	   	   	 	dp[l]=a;
				}
		   }
	     	
		 }
	   	
	   }
	   cout<<dp[n-1];
	   
      }
	} 
	
	
	

Measured memory_bytes: 4748
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<62)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll h,n;
    cin>>h>>n;
    vl a(n),b(n);
    rep(i,n){
        cin>>a[i]>>b[i];
    }
    
    //vll cost(n,h+1);
    vl dp(h+10001,LINF);
    dp[0]=0;
    ll sample=LINF,ans=LINF;
    
    rep(i,n){
        rep(j,h+10001){
            if(j>=a[i]){
                sample=dp[j-(a[i])] + b[i];
                dp[j]=min(dp[j],sample);
            }
        }
    }
    
    range(i,h,h+10001){
        ans=min(ans,dp[i]);
    }
    puta(ans);
    
    
}

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

using namespace std;

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef vector<int> vi;

inline void fileIO(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

template <class T, class S>
inline bool smin(T &a, S b) {
  return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
  return a < (T)b ? a = b, 1 : 0;
}

constexpr int MOD = 924844033;
constexpr int N = 2e3 + 10;

template <typename T>
inline T mod(T &v) {
  return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
  return mod(l += r);
}

int n, k;
ll dp[N << 1][N][2], fact[N];

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

#ifndef LOCAL
  // fileIO("superposition");
#endif

  fact[0] = dp[0][0][1] = 1;
  rep(i, 1, N) add(fact[i], fact[i - 1] * i);
  cin >> n >> k;
  int cnt = 0;
  rep(i, 0, k) {
    int me = i;
    while (me < n) {
      cnt++;
      for (int j = 0; 2 * j <= cnt; j++) {
        add(dp[cnt][j][0], dp[cnt - 1][j][0] + dp[cnt - 1][j][1]);
        if (me != i && j) add(dp[cnt][j][1], dp[cnt - 1][j - 1][0]);
      }
      me += k;
    }
    me = i;
    while (me < n) {
      cnt++;
      for (int j = 0; 2 * j <= cnt; j++) {
        add(dp[cnt][j][0], dp[cnt - 1][j][0] + dp[cnt - 1][j][1]);
        if (me != i && j) add(dp[cnt][j][1], dp[cnt - 1][j - 1][0]);
      }
      me += k;
    }
  }

  ll answer = 0;
  rep(i, 0, n + 1) {
    add(answer,
        (i & 1 ? -1 : 1) * fact[n - i] * (dp[cnt][i][0] + dp[cnt][i][1]));
  }

  cout << answer << endl;

  return 0;
}

Measured memory_bytes: 124160
import math

while True:
    n = int(input())
    if n==0:
        break
    an = list(map(int, input().split()))
    mean = sum(an)/n
    v = sum(list(map(lambda x: (x-mean)**2, an)))/n
    std = math.sqrt(v)
    print(round(std,6))
    
    


Measured memory_bytes: 5704
n, y = map(int, input().split())
ans =0
o10000=-1
o5000=-1
o1000=-1
for i in range(n+1):
    for j in range(n+1-i):
        k = n - i - j
        ans = 10000*i + 5000*j + 1000*k
        if ans == y:
            o10000=i
            o5000=j
            o1000=k
            break
print(o10000, o5000, o1000)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=3.14159265359;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
void SRAND(){auto duration = std::chrono::system_clock::now().time_since_epoch();auto millis = std::chrono::duration_cast<std::chrono::milliseconds>(duration).count();srand(millis);}

ll n,k,a,b,x,l,r;
string s;
vector<ll> v;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	cin>>s;
	if(n==1){cout<<0;return 0;}
	REP(i,SZ(s)){
		if(i==0)x++;
		else if(s[i]!=s[i-1]){
			if(s[i-1]=='L')l++;else r++;
			v.pb(x);
			x=1;
		}else x++;
	}
	if(s[SZ(s)-1]=='L')l++;else r++;
	v.pb(x);
	x=0;
	for(ll i:v)x+=i-1;
	l=l*2-(s[0]=='L'?1:0)-(s[SZ(s)-1]=='L'?1:0);
	r=r*2-(s[0]=='R'?1:0)-(s[SZ(s)-1]=='R'?1:0);
	cout<<x+max(min(k*2,l),min(k*2,r));
	return 0;
}


Measured memory_bytes: 1480
from itertools import product
n, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(n)]
# 3:A 2:B 1:C 0:使わない
ans = float("inf")
use_list = list(product(range(4), repeat=n))
#print(use_list)
for take_use in use_list:
    a, b, c = 0, 0, 0
    count_a, count_b, count_c = 0, 0, 0
    cost = 0
    for j in range(n):
        if take_use[j] == 3:
            a += l[j]
            count_a += 1
        elif take_use[j] == 2:
            b += l[j]
            count_b += 1
        elif take_use[j] == 1:
            c += l[j]
            count_c += 1
    if count_a == 0 or count_b == 0 or count_c == 0:
        continue
    cost += (count_a-1 + count_b-1 + count_c-1)*10
    cost += abs(A-a) + abs(B-b) + abs(C-c)
    ans = min(ans, cost)
print(ans)


Measured memory_bytes: 84244
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<queue>
#include<cassert>
#include<tuple>
#include<set>
#include<map>
#include<list>
#include<bitset>

#define PB push_back
#define ALL(a)  (a).begin(),(a).end()
#define DWN(a)  (a).begin(),(a).end(), greater<int>()
#define rep(i, m) for (int i = 0; i < m; i++)
#define REP(i, n, m) for (int i = n; i < m; i++)

#define mod 1000000007

using namespace std;

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

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
const int INF = (int)1e9;

int main()
{
	int N, K; cin >> N >> K;
	vector<ll> x(N), y(N);
	rep(i, N) {
		cin >> x[i] >> y[i];
	}
	ll ans = 4e18;
	//x方向の2つの点
	rep(i, N) {
		rep(j, N) {
			if (i == j || x[i] >= x[j]) continue;
			//y方向の2つの点
			rep(k, N) {
				rep(l, N) {
					if (k == l || y[k] <= y[l]) continue;
					//x[j]が右の点、x[i]が左の点
					//y[k]が上の点、y[l]が下の点
					//x,y方向の範囲を狭めていく
					if (x[i] <= x[k] && x[j] >= x[k] && x[i] <= x[l] && x[j] >= x[l]) {
						if (y[i] <= y[k] && y[i] >= y[l] && y[j] <= y[k] && y[j] >= y[l]) {
							int cnt = 0; //点の数を数える
							
							rep(c, N) {
								//点が範囲内にあるか
								if (x[i] <= x[c] && x[c] <= x[j] && y[l] <= y[c] && y[c] <= y[k]) cnt++;
							}
							
							if (cnt >= K) { //点の数がK以上であるとき
								ans = min(ans, (x[j] - x[i]) * (y[k] - y[l])); //最小の面積
							}
						}
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dp[200005][3];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int b[3];
        int j,k,l;
        for(j=0;j<3;j++)
        cin>>b[j];
        for(j=0;j<3;j++)
        {
            for(k=0;k<3;k++)
            {
                if(j!=k)
                dp[i+1][j]=max(dp[i+1][j],dp[i][k]+b[j]);
            }
        }
    }
    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
}

Measured memory_bytes: 1408
import math

N = int(input())

goal_x = 1
goal_y = N

for i in range(2, int(math.sqrt(N) + 1)):
    if N % i == 0:
        if goal_x + goal_y > i + int(N / i):
            goal_x = i
            goal_y = int(N / i)

print(goal_x + goal_y - 2)


Measured memory_bytes: 2940
import sys
sys.setrecursionlimit(10**7)
N, K = map(int, input().split())
S = input()

cnt1 = 0
cnt2 = 0

for i in range(N-1):
    # edge
    if i == 0 and S[i] == 'L':
        cnt1 += 1
    if i == N-2 and S[i+1] == 'R':
        cnt1 += 1 

    # not edge
    if S[i] == S[i+1]:
        continue
    elif S[i] == 'L' and S[i+1] == 'R':
        continue
    elif S[i] == 'R' and S[i+1] == 'L':
        cnt2 += 1

if cnt2 >= K:
    print(min(N-1, N - (cnt2-K)*2 - cnt1))
else:
    print(min(N-1, N - max(0, (cnt1 - (K - cnt2)))))


Measured memory_bytes: 3316
import sys
import math

A, B, H, M = map(int, sys.stdin.readline().split())
theta = (H * 30 + M * 0.5)  - (M * 6)
ans = math.sqrt((A**2 + B**2) - (2 * A * B) * math.cos(math.radians(theta)))
print('{:.20f}'.format(ans))

Measured memory_bytes: 9428
#include <stdio.h>
#include <string.h>

typedef struct {
  char name[100];
  int t;
}A;

A Q[1000000];
A P[1000000];
int head, tail, n;

int isEmpty(){
  if(head == tail)return 1;
  else return 0;
}

void queue(A x){
  Q[tail] = x;
  tail++;
}

void initialize(){
  head = 0;
  tail = n+1;
}


int main(){
  int i, q, count=1, tmp=0, c;
  
  scanf("%d%d",&n,&q);
  int a[n+1];
  
  for(i=1; i<=n; i++)
    P[i].t = 0;

  for(i=1; i<=n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  initialize();

  i=1;

  while(count != n+1){
    if(Q[i].t > q){
      Q[i].t=Q[i].t-q;
      tmp += q;
      queue(Q[i]);
      i++;
    }
    else if(Q[i].t<=q){
      tmp += Q[i].t;
      P[count].t=tmp;
      strcpy(P[count].name, Q[i].name);
      i++;
     
      count++;
    }
  }

  for(i=1; i<=n; i++)
    printf("%s %d\n",P[i].name,P[i].t);
    
  return 0;
}
  



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

int main() {
    int a,b,v,w;
    ll t;
    cin>>a>>v;
    cin>>b>>w;
    cin>>t;
    if(abs(a-b)<=t*abs(v-w)&&v>w){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}

Measured memory_bytes: 3636
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
for i in range(n):
    if a[i] > b[i]:
        ans += b[i]
        a[i] = a[i] - b[i]
    elif a[i] == b[i]:
        ans += b[i]
        a[i] = 0
    elif a[i] < b[i]:
        ans += a[i]
        if (a[i + 1] - (b[i] - a[i])) <= 0:
            ans += a[i + 1]
            a[i + 1] = 0
        else:
            a[i + 1] = a[i + 1] - (b[i] - a[i])
            ans += b[i] - a[i]
        a[i] = 0
print(ans)


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

#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

#define int long long
using namespace std;
const int INF = 2e18;
const int MOD = 1e9 + 7;
const int MB = 60;

int mod_pow(int a, int b) {
	if (!b) return 1;
	if (b % 2) return a * mod_pow(a, b - 1) % MOD;
	int q = mod_pow(a, b / 2);
	return q * q % MOD;
}

void solve() {
	int h, w;
	cin >> h >> w;
	int n;
	cin >> n;
	vector < pair<int, int>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	a.pb({ h, w });
	sort(all(a));

	vector<int> fact(h + w);
	fact[0] = 1;
	for (int i = 1; i < fact.size(); i++) {
		fact[i] = fact[i - 1] * i % MOD;
	}

	vector<int> inv(h + w);
	for (int i = 0; i < inv.size(); i++) {
		inv[i] = mod_pow(fact[i], MOD - 2);
	}

	vector<int> dp(n + 1);
	for (int i = 0; i <= n; i++) {
		dp[i] = (fact[a[i].first + a[i].second - 2] * inv[a[i].first - 1] % MOD) * inv[a[i].second - 1] % MOD;
		for (int j = 0; j < i; j++) {
			if (a[j].second <= a[i].second) {
				int x = a[i].first - a[j].first + 1;
				int y = a[i].second - a[j].second + 1;
				int v = (fact[x + y - 2] * inv[x - 1] % MOD) * inv[y - 1] % MOD;
				dp[i] = (dp[i] - v * dp[j] % MOD + MOD) % MOD;
			}
		}
	}
	cout << dp[n];
}

signed main() {
	/*
	freopen("search.in", "r", stdin);
	freopen("search.out", "w", stdout);
	*/
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	solve();
}


Measured memory_bytes: 3456
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(V) sort((V).begin(),(V).end())
#define pb push_back
#define endl '\n'
#define int long long

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

// 変数定義
char s;
//

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> s;
  int c = 0;
  for(char i = s; i <= 'z'; i++) {
    s = i;
    if(c==1) break;
    c++;
  }
  cout << s << endl;
}

Measured memory_bytes: 256
H, W = map(int, input().split())

C = []

for i in range(H):
    temp = input()

    for i in temp:
        if i != '.':
            C.append(temp)
            break

WB = [0] * W

for i in range(len(C)):
    for j in range(W):
        if C[i][j] == '.':
            WB[j] += 1

for i in range(len(C)):
    for j in range(W):
        if WB[j] != len(C):
            print(C[i][j], end='')
    print()


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

int main() {
    int n, sum, minv = 100001;
    cin >> n;
    vector<int> w(n);
    for (int i = 0; i < w.size(); i++)
    {
        cin >> w[i];
    }
    
    for (int i = 0; i < n - 1; i++)
    {
        int lsum = 0, rsum = 0;
        for (int j = 0; j < i + 1; j++)
        {
            lsum += w[j];
        }
        for (int k = i + 1; k < n; k++)
        {
            rsum += w[k];
        }
        sum = abs(lsum - rsum);
        minv = min(minv, sum);
    }
    cout << minv << endl;
}

Measured memory_bytes: 256
n, m = [int(i) for i in input().split()]

l = []
r = []
for _ in range(m):
  l_tmp, r_tmp = [int(i) for i in input().split()]
  l.append(l_tmp)
  r.append(r_tmp)
  
l_max = max(l)
r_min = min(r)

ans = r_min - l_max + 1

if ans > 0:
  print(ans)
else:
  print(0)


Measured memory_bytes: 11084
#include<iostream>

#define INFINITY 1000000001

using namespace std;


long long merge(int*, int left, int mid, int right);
long long mergeSort(int*, int left, int right);

int main() {
	int n;
	cin >> n;
	int* a = new int[n];
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
	long long count = mergeSort(a, 0, n);
	cout << count << endl;
}

long long merge(int* a, int left, int mid, int right) {
	long long count = 0;
	int* l, * r;
	l = new int[mid - left + 1];
	r = new int[right - mid + 1];
	for (int i = 0;i < mid - left;i++) {
		l[i] = a[i + left];
	}
	for (int i = 0;i < right - mid;i++) {
		r[i] = a[mid + i];
	}
	l[mid - left] = r[right - mid] = INFINITY;
	int j = 0, k = 0;
	for (int i = 0;i < right - left;i++) {
		if (l[j] <= r[k]) {
			a[left + i] = l[j];
			j++;
			count += k;
		}
		else {
			a[left + i] = r[k];
			k++;
		}
	}
	return count;
}

long long mergeSort(int* a, int left, int right) {
	if (right - left <= 1)return 0;
	long long count = 0;
	int mid = (left + right) / 2;
	count += mergeSort(a, left, mid);
	count += mergeSort(a, mid, right);
	count += merge(a, left, mid, right);
	return count;
}


Measured memory_bytes: 27296
#include <iostream>
#include <cmath>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	if(abs(a-b)%2==0){
		cout<<min(a,b)+abs(a-b)/2<<endl;
	}
	else{
		cout<<"IMPOSSIBLE"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
// kort0n
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i; 
const long long INF = 1e18;
//const ll mod = 1000000007;
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll ans = 0;
    for(ll i = 2; i * i <= N; i++) {
        if(N % i != 0) continue;
        ll num = 0;
        while(N % i == 0) {
            N /= i;
            num++;
        }
        for(ll j = 1; ; j++) {
            if(num >= j) {
                num -= j;
                ans++;
            } else break;
        }
    }
    if(N != 1) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
s=input()
n=len(s)
li=[]
for i in range(n):
  if s[i]=="A" or s[i]=="T" or s[i]=="C" or s[i]=="G":
    li.append(s[i])
  else:
    li.append("0")
t=""
for i in range(n):
  t+=li[i]
a = list(map(len,t.split("0")))
a.sort()
print(a[-1])

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

int main() {
    int N, M, C;
    cin >> N >> M >> C;

    int B[M];
    for (int i = 0; i < M; ++i) cin >> B[i];

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

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        int t = 0;
        for (int j = 0; j < M; ++j) {
            t += A[i][j] * B[j];
        }

        if (t + C > 0) ans++;
    }

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

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


vector<ll> solve(ll D, ll Z, vector<ll>& C, vector<vector<ll>>& S, vector<int>& T, ll M, vector<int>& d, vector<int>& q) { 
    ll v = 0;
    vector<set<int>> e(Z);
    for ( int i = 0; i < Z; i++ ) {
        e[i].insert(-1);
        e[i].insert(D);
    }
    for ( int d = 0; d < D; d++ ) {
        int t = T[d];
        v += S[d][t];
        e[t].insert(d);
    }
    for ( int i = 0; i < Z; i++ ) {
        auto p0 = e[i].begin();
        auto p1 = next(p0);
        while ( p1 != e[i].end() ) {
            ll df = *p1 - *p0;
            v -= df*(df-1)/2 * C[i];
            p0 = p1;
            p1 = next(p0);
        }
    }

    vector<ll> V(M);
    vector<int> TT(T);
    for ( int m = 0; m < M; m++ ) {
        int dd = d[m];
        int t0 = TT[dd], t1 = q[m];
        auto p1 = e[t0].find(dd);
        auto p0 = prev(p1), p2 = next(p1);
        v -= (*p1 - *p0) * (*p2 - *p1) * C[t0];
        v -= S[dd][t0];

        e[t0].erase(dd);
        e[t1].insert(dd);
        TT[dd] = t1;

        p1 = e[t1].find(dd);
        p0 = prev(p1), p2 = next(p1);
        v += (*p1 - *p0) * (*p2 - *p1) * C[t1];
        v += S[dd][t1];

        V[m] = v;
    }
    return V;
}

// vector<ll> score(ll D, ll Z, vector<ll>& C, vector<vector<ll>>& S, vector<int>& T) {
//     vector<ll> V(D), L(Z);
//     ll v = 0;
//     for ( int d = 0; d < D; d++ ) {
//         int t = T[d];
//         ll dv = S[d][t];
//         for ( int i = 0; i < Z; i++ ) {
//             L[i] += C[i];
//             dv -= L[i];
//         }
//         dv += L[t];
//         L[t] = 0;
//         v += dv;
//         V[d] = v;
//     }
//     return V;
// }

int main() {
    ll D, Z = 26;
    cin >> D;
    vector<ll> C(Z);
    for ( int i = 0; i < Z; i++ ) {
        cin >> C[i];
    }
    vector<vector<ll>> S(D, vector<ll>(Z));
    for ( int i = 0; i < D; i++ ) {
        for ( int j = 0; j < Z; j++ ) {
            cin >> S[i][j];
        }
    }
    vector<int> T(D);
    for ( int i = 0; i < D; i++ ) {
        cin >> T[i];
        T[i]--;
    }
    ll M;
    cin >> M;
    vector<int> d(M), q(M);
    for ( int m = 0; m < M; m++ ) {
        cin >> d[m] >> q[m];
        d[m]--, q[m]--;
    }


    vector<ll> V = solve(D, Z, C, S, T, M, d, q);
    for ( int i = 0; i < M; i++ ) {
        cout << V[i] << "\n";
    }
    return 0;
}

Measured memory_bytes: 4688
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

#define rep(i,st,ed) for (int i=st;i<=ed;++i)

typedef long long LL;
const LL INF=1e18;
const int N=200005;

std:: vector <int> E[N],G[N];

LL a[N],b[N],f[N],g[N];
int fa[N],rk[N];

bool vis[N];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):v,ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void dfs(int x) {
	if (G[x].empty()) {
		f[x]=a[x]+b[x],g[x]=b[x];
		return ;
	}
	g[x]=b[x],f[x]=INF;
	for (int y:G[x]) dfs(y),g[x]+=g[y];
	for (int y:G[x]) {
		f[x]=std:: min(f[x],std:: max(f[y],a[x])+g[x]-g[y]);
	}
}

int find(int x) {
	return !fa[x]?x:(fa[x]=find(fa[x]));
}

bool cmp(int x,int y) {
	return a[x]<a[y];
}

int main(void) {
	int n=read(),m=read();
	rep(i,1,n) {
		a[i]=read(),b[i]=read();
		a[i]=std:: max(a[i]-b[i],0LL);
		rk[i]=i;
	}
	rep(i,1,m) {
		int x=read(),y=read();
		E[x].push_back(y);
		E[y].push_back(x);
	}
	std:: sort(rk+1,rk+n+1,cmp);
	rep(ti,1,n) {
		int x=rk[ti]; vis[x]=1;
		for (int y:E[x]) {
			if (!vis[y]) continue;
			if (find(y)==find(x)) continue;
			G[x].push_back(find(y));
			fa[find(y)]=find(x);
		}
	}
	rep(i,1,n) if (find(i)==i) {
		dfs(i),printf("%lld\n", f[i]);
	}
	return 0;
}

Measured memory_bytes: 26748
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
#define free  freopen ("input.txt", "r", stdin);freopen ("output.txt", "w", stdout);
#define Fast  ios::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second

bool vowel(char che)
{
    if (che == 'A' || che == 'E' || che == 'I' || che == 'O' || che == 'U' || che == 'Y')
        return true;
    else
        return false;
}

const int N = 3e5+5;
const int mod = 1e9+7;
ll a[N], b[N], c[N], d, dp1, dis;
char o;
bool mark[N], h;
string s;
//set <ll> st1, st2;
//deque <int> dq;
//vector <ll> vm, vp, vt[N];
//int a1[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};


int main()
{
    Fast
    ll t, n, m, k = 0, f = 0, sum = 0, ans = 0;
    cin >> n;
    cout << 1-n;
}


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

int main(){
    int n;
    cin >> n;
    int y;
    cin >> y;

    rep(i,2001){
        rep(j,2001){
            rep(k,n-i-j+1){
                if (10000*i + 5000*j + 1000*k == y && i + j + k == n){
                    cout << i << " " << j << " " << k << endl;
                    return 0;
                }
            }
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
n = gets.to_i
index_of = (1..n).to_a.permutation(n).map{|it| it.join('')}.sort.each_with_index.to_h{|it, i| [it, i]}

a = gets.chomp.split.join('')
b = gets.chomp.split.join('')
puts (index_of[a] - index_of[b]).abs


Measured memory_bytes: 24196
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.math;
import std.regex;
import std.range;

void main() {
	auto N = readln.chomp.to!int;
	auto A1 = readln.split.to!(int[]);
	auto A2 = readln.split.to!(int[]);
	
	int res;
	int tmp;
	foreach(i; 0..N) {
		tmp += A1[i];
		res = max(res, tmp+A2[i..N].sum);
	}
	res.writeln;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
int main()
{
	string s;
	cin>>s;
	bool rny=1;
	int count=0;
	int ans=count;
	for(char c:s){
		if(c=='R'){
		rny=1;
		if(rny==1)
			count++;
ans=max(count,ans);
		}
		else{
			count=0;
			rny=0;
		}
	}
cout<<ans;
        	
}






Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vii;
typedef vector<ll> vll;

#define X first
#define Y second
#define rep(i,n) for(ll i=0; i<(n); i++)
#define repp(i,ed,b) for(ll i=ed; i<=(b); i++)
#define repp2(i,b,ed) for(ll i=b; i>=(ed); i--)
#define fill(ed,val) memset(ed, (val), sizeof(ed))
#define mp make_pair
#define pb push_back
#define sz(x) (ll)x.size()
#define all(c) (c).begin(), (c).end()
#define uni(c) c.resize(distance(c.begin(), unique(all(c))))
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sc(n) scanf("%lld",&n)

ll mod= 1e9 + 7, mod1=1e9+9;
const ll N=100005,MAX=2e9+5;



int main()
{   
    io;
    
    vector<pll> v;
    ll n,m;
    cin>>n>>m;
    rep(i,n){
        ll x;
        cin>>x;
        v.pb(mp(x,0));
    }
    
    rep(i,m){
        ll x;
        cin>>x;
        v.pb(mp(x,1));
    }
    
    sort(all(v));
    ll ro=0,co=0,ans=0;
    for(auto x:v){
        ll a=x.X,c=(x.Y);
        //cout<<a<<' '<<c<<endl;
        if(c==0){
            ans+=(m+1-co)*a;
            ro++;
        }
        else{
            ans+=(n+1-ro)*a;
            co++;
        }
    }
    cout<<ans;
    
    return 0;
}

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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define dump(x)  cout << #x << " = " << (x) << endl;	//debug
#define SZ(x) ((int)(x).size())
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define ps(s) cout << #s << endl;
#define pv(v) cout << (v) << endl;
#define ALL(a)  (a).begin(),(a).end()
#define RANGE(a, l, r)  (a).begin()+(l),(a).begin()+(r)

int main() {
	queue<ll> que;
	que.push(1);
	que.push(2);
	que.push(3);
	que.push(4);
	que.push(5);
	que.push(6);
	que.push(7);
	que.push(8);
	que.push(9);
	int k;
	cin >> k;
	ll res;
	FOR(i, 1, k) {
		res = que.front();
		que.pop();
		int ldigit = res % 10;
		switch (ldigit)
		{
		case 0:
			que.push(res * 10 + ldigit);
			que.push(res * 10 + ldigit + 1);
			break;
		case 1:
		case 2:
		case 3:
		case 4:
		case 5:
		case 6:
		case 7:
		case 8:
			que.push(res * 10 + ldigit - 1);
			que.push(res * 10 + ldigit);
			que.push(res * 10 + ldigit + 1);
			break;
		case 9:
			que.push(res * 10 + ldigit - 1);
			que.push(res * 10 + ldigit);
			break;
		default:
			break;
		}
	}
	pv(res)
}

Measured memory_bytes: 5092