Submission #1189253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189253		misavo	시간이 돈 (balkan11_timeismoney)	C++20	5 / 100	12 ms	584 KiB

timeismoney

#include <bits/stdc++.h>
// #include <iostream>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define sz(x) int((x).size())
#define all(a) begin(a), end(a)
#define pll pair<long long, long long>
#define vb vector<bool>
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define vpl vector< pair<long long, long long> >
#define f(i,s,e) for(long long int i = s; i < e; i++)
#define cf(i,s,e) for(long long int i = s; i <= e; i++)
#define rf(i,s,e) for(long long int i = s; i >= e; i--)
#define print(a) for(auto x : a) cout << x << " " <<endl;
#define printp(a) for(auto x : a) cout << x.first << " " << x.second <<endl;
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

inline ll read() {ll x = 0, fh = 1; char ch = getchar(); while(!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();} while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();} return x*fh;}

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

ll t, n, m, k, a, b, tot;
string s;
ll edges[10009][4];
bool used[10009], connect[209];

void solve() {
    cin >> n >> m;
    f(i, 0, m) {
        cin >> a >> b >> t >> k;
        edges[i][0] = a;
        edges[i][1] = b;
        edges[i][2] = t;
        edges[i][3] = k;
    }

    ll time = 0, cost = 0;
    f(i, 0, n-1) {
        ll idx = 0, mn = LLONG_MAX;
        f(j, 0, m) {
            if (!used[j]) {
                if (!connect[edges[j][0]] && !connect[edges[j][1]] && time > 0) continue;
                if ((time + edges[j][2]) * (cost + edges[j][3]) < mn) {
                    mn = (time + edges[j][2]) * (cost + edges[j][3]);
                    idx = j;
                }
            }
        } 
        
        used[idx] = 1;
        connect[edges[idx][0]] = 1;
        connect[edges[idx][1]] = 1;
        time += edges[idx][2];
        cost += edges[idx][3];
    }

    cout << time << " " << cost <<endl;
    f(i, 0, m) if (used[i]) cout << edges[i][0] << " " << edges[i][1] <<endl;
}

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

    solve();
}

• Subtask 1: 5 / 100